Submission #1181614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181614		AMnu	Minerals (JOI19_minerals)	C++20	40 / 100	29 ms	6024 KiB

minerals

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

const int MAXN = 9e4;

int last, P, L[MAXN], R[MAXN];
bool in[MAXN], rig;
vector <int> V[2], mid[MAXN];

// int Query(int x);
// void Answer(int x, int y);

// is the pair of x inside?
bool check(int x) {
    int cur = Query(x);
    in[x] = !in[x];
    if (cur == last) {
        return true;
    }
    last = cur;
    return false;
}

void Solve(int N) {
    for (int i=1;i<=2*N;i++) {
        bool x = check(i);
        if (x) {
            int j = V[1].size();
            L[j] = 0;
            R[j] = V[0].size()-1;
            // cout << i << " " << L[j] << " " << R[j] << "\n";
            if (L[j] == R[j]) {
                Answer(V[0][L[j]],i);
                P++;
            }
            else {
                mid[(L[j]+R[j])/2].push_back(j);
            }
        }
        V[x].push_back(i);
    }
    // for (int x : V[0]) cout << x << " "; cout << "\n";
    // for (int x : V[1]) cout << x << " "; cout << "\n";
    while (P < N) {
        rig = !rig;
        for (int i=0;i<N;i++) {
            check(V[0][i]);
            for (int j : mid[i]) {
                if (check(V[1][j])^rig) {
                    R[j] = i;
                }
                else {
                    L[j] = i+1;
                }
                // cout << V[1][j] << " " << L[j] << " " << R[j] << "\n";
                if (L[j] == R[j]) {
                    Answer(V[0][L[j]],V[1][j]);
                    P++;
                }
                else {
                    mid[(L[j]+R[j])/2].push_back(j);
                }
            }
            mid[i].clear();
        }
    }
}

• 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