Submission #1128640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128640		vladilius	Minerals (JOI19_minerals)	C++20	70 / 100	24 ms	2568 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

void Solve(int n){
    vector<bool> us(2 * n + 1);
    int S = 0;
    for (int i = 1; i <= 2 * n; i++){
        if (Query(i) > S){
            S++;
            us[i] = 1;
        }
    }

    vector<int> lf = {0}, rr;
    for (int i = 1; i <= 2 * n; i++){
        if (us[i]){
            lf.pb(i);
            continue;
        }
        rr.pb(i);
    }
    
    for (int i = 1; i <= n; i++) Query(lf[i]);
    
    vector<bool> U(2 * n + 1);
    int tr = 0;
    S = n;
    function<void(int, int, vector<int>)> solve = [&](int l, int r, vector<int> f){
        if (f.empty()) return;
        if (l == r){
            Answer(lf[l], f[0]);
            return;
        }
        int m = (l + r) / 2;

        while (tr < m){
            S = Query(lf[++tr]);
        }
        while (tr > m){
            S = Query(lf[tr--]);
        }
        
        vector<int> left, right;
        for (int i: f){
            int S1 = Query(i);
            if (S1 == S){
                left.pb(i);
            }
            else {
                S = S1;
                right.pb(i);
            }
        }
        
        solve(m + 1, r, right);
        solve(l, m, left);
    };
    
    solve(1, n, rr);
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10