Submission #1189579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189579		onbert	Minerals (JOI19_minerals)	C++20	100 / 100	28 ms	4328 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 << p[i] << " "; cout << endl;
    // for (int i:R) cout << i << " "; cout << endl;
    int Lsz = max(3*sz/8, (int)1);
    if (p[L[0]] == p[L[1]]) int trash = put(L[0]);
    for (int i=1;i<Lsz;i++) int trash = put(L[i]);
    // for (int i=1;i<=2*n;i++) cout << p[i] << " "; cout << endl;
    vector<int> ll[2], rr[2];
    for (int i:L) ll[p[i]].push_back(i);
    for (int i=1;i<sz;i++) {
        rr[!abs(put(R[i]))].push_back(R[i]);
    }
    if (rr[0].size() < ll[0].size()) {
        rr[0].push_back(R[0]);
        swap(rr[0][0], rr[0].back());
    } else {
        rr[1].push_back(R[0]);
        swap(rr[1][0], rr[1].back());
    }
    solve(rr[0], ll[0]); solve(rr[1], ll[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: 5 / 5
• Subtask 9: 10 / 10