# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1128622 | vladilius | Minerals (JOI19_minerals) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
void solve(int n){
used.resize(2 * n + 1);
cnt.resize(n + 1);
cc = 0;
int tl = 1, tr = 0, S = 0;
function<void(int, int, vector<int>)> solve = [&](int l, int r, vector<int> f){
if (f.empty()) return;
if (l == r){
Answer(f[0], f[1]);
return;
}
int m = (l + r) / 2;
while (tr < m){
tr++;
S = Query(tr);
}
while (tl > l){
tl--;
S = Query(tl);
}
while (tr > m){
S = Query(tr--);
}
while (tl < l){
S = Query(tl++);
}
vector<int> left, right;
for (int i: f){
if (i <= m){
left.pb(i);
continue;
}
int S1 = Query(i);
if (S == S1){
left.pb(i);
}
else {
right.pb(i);
}
Query(i);
}
solve(l, m, left);
solve(m + 1, r, right);
};
vector<int> all;
for (int i = 1; i <= 2 * n; i++) all.pb(i);
solve(1, 2 * n, all);
}