Submission #1189545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189545		onbert	Minerals (JOI19_minerals)	C++20	85 / 100	26 ms	3952 KiB

minerals

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

const int maxn = 86005;
int n;
bool p[maxn];
int verd;
vector<pair<int,int>> ans;

int put(int x) {
    int ori = verd;
    verd = Query(x);
    p[x] = !p[x];
    // cout << "Q " << x << " " << verd << " " << ori << " " << verd - ori << endl;
    return verd - ori;
}

void solve(vector<int> L, vector<int> R) {
    int sz = L.size();
    if (sz == 1) {
        ans.push_back({L[0], R[0]});
        return;
    }
    // cout << "TEST " << sz << endl;
    // for (int i:L) cout << i << " "; cout << endl;
    // for (int i:R) cout << i << " "; cout << endl;
    vector<int> ll[2], rr[2];
    for (int i=0;i<sz/2;i++) int trash = put(L[i]);
    // for (int i=1;i<=2*n;i++) cout << p[i] << " "; cout << endl;
    for (int i:L) ll[p[i]].push_back(i);
    for (int i=0;i<sz-1;i++) {
        rr[!abs(put(R[i]))].push_back(R[i]);
    }
    if (rr[0].size() < ll[0].size()) rr[0].push_back(R.back());
    else rr[1].push_back(R.back());
    solve(ll[0], rr[0]); solve(ll[1], rr[1]);
}

void Solve(int N) {
    n = N, verd = 0;
    ans.clear();
    for (int i=1;i<=2*n;i++) p[i] = false;
    vector<int> L, R;
    for (int i=1;i<=2*n;i++) {
        if (put(i)) R.push_back(i);
        else L.push_back(i);
    }
    solve(L, R);
    for (auto [x, y]:ans) Answer(x, y);
}

• 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