Submission #1128650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128650		vladilius	Minerals (JOI19_minerals)	C++20	85 / 100	27 ms	2784 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);
    }
    
    int tr = n;
    S = n;
    function<void(int, int, vector<int>)> solve = [&](int l, int r, vector<int> f){
        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 j = 0; j + 1 < f.size(); j++){
            int i = f[j];
            if (left.size() == (m - l + 1)){
                right.pb(i);
                continue;
            }
            if (right.size() == (r - m)){
                left.pb(i);
                continue;
            }
            int S1 = Query(i);
            if (S1 == S){
                left.pb(i);
            }
            else {
                S = S1;
                right.pb(i);
            }
        }
        
        if (left.size() <= (m - l)) left.pb(f.back());
        else right.pb(f.back());
        
        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: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10