Submission #1190237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190237		Ghulam_Junaid	Minerals (JOI19_minerals)	C++20	40 / 100	44 ms	9084 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MXN = 1e5 + 100;
int n, lo[MXN], hi[MXN];
vector<int> a, b, vec[MXN];
set<int> M;

void Solve(int nn){
    srand(time(NULL));

    n = nn;

    vector<int> S;
    for (int i = 1; i <= 2 * n; i ++)
        S.push_back(i);
    for (int i = 2 * n; i > 0; i --)
        swap(S[i - 1], S[rng() % i]);

    int D = 0;
    for (int i : S){
        if (Query(i) == D){
            b.push_back(i);
        }
        else{
            D++;
            a.push_back(i);
        }
    }

    for (int i : a){
        lo[i] = -1;
        hi[i] = n - 1;
    }

    for (int i : a){
        if (hi[i] - lo[i] <= 1) continue;
        int mid = (lo[i] + hi[i]) / 2;
        vec[mid].push_back(i);
        M.insert(mid);
    }

    int it = 1;
    int fst = 0, lst = n - 1;
    while (!M.empty()){
        it++;        
        if (it % 2 == 1){
            for (int i = fst; i < n; i ++){
                D = Query(b[i]);
                int tmpD;
                for (int x : vec[i]){
                    tmpD = Query(x);
                    if (tmpD == D)
                        hi[x] = i;
                    else
                        lo[x] = i;
                    D = tmpD;

                    if (hi[x] - lo[x] > 1){
                        int mid = (lo[x] + hi[x]) / 2;
                        vec[mid].push_back(x);
                        M.insert(mid);
                    }
                }
                M.erase(i);
                vec[i].clear();

                lst = i;
                if (M.empty() or (*M.rbegin()) <= i)
                    break;
            }
        }
        else{
            int tmpD;
            for (int i = lst; i >= 0; i --){
                for (int x : vec[i]){
                    tmpD = Query(x);
                    if (tmpD == D)
                        hi[x] = i;
                    else
                        lo[x] = i;
                    D = tmpD;

                    if (hi[x] - lo[x] > 1){
                        int mid = (lo[x] + hi[x]) / 2;
                        vec[mid].push_back(x);
                        M.insert(mid);
                    }
                }
                M.erase(i);
                vec[i].clear();
                D = Query(b[i]);

                fst = i;
                if (M.empty() or *M.begin() >= i)
                    break;
            }
        }
    }

    for (int i : a)
        Answer(i, b[hi[i]]);
}

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