Submission #1190143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190143		Ghulam_Junaid	Minerals (JOI19_minerals)	C++20	40 / 100	30 ms	6124 KiB

minerals

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

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

void Solve(int nn){
    n = nn;

    int D = 0;
    for (int i = 1; i <= 2 * n; i ++){
        if (Query(i) == D){
            b.push_back(i);
            Query(i);
        }
        else{
            D++;
            a.push_back(i);
        }
    }

    for (int i : a){
        int lb = lower_bound(b.begin(), b.end(), i) - b.begin();
        lo[i] = lb - 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);
    }

    for (int it = 0; it < 16; it ++){        
        if (it % 2 == 0){
            for (int i = 0; i < n; i ++){
                int 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);
                    }
                }
                vec[i].clear();
            }
        }
        else{
            int D = n, tmpD;
            for (int i = n - 1; 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);
                    }
                }
                vec[i].clear();
                D = Query(b[i]);
            }
        }
    }

    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