#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MXN = 1e5 + 100;
int n, lo[MXN], hi[MXN];
vector<int> a, b, vec[MXN];
set<int> M;
void Solve(int nn){
srand(time(NULL));
n = nn;
vector<int> S;
for (int i = 1; i <= 2 * n; i ++)
S.push_back(i);
for (int i = 2 * n; i > 0; i --)
swap(S[i - 1], S[rng() % i]);
int D = 0;
for (int i : S){
if (Query(i) == D){
b.push_back(i);
}
else{
D++;
a.push_back(i);
}
}
for (int i : a){
lo[i] = -1;
hi[i] = n - 1;
}
for (int i : a){
if (hi[i] - lo[i] <= 1) continue;
int mid = (lo[i] + hi[i]) / 2;
M.insert(mid);
vec[mid].push_back(i);
}
int it = 1;
int fst = 0, lst = n - 1;
while (!M.empty()){
it++;
if (it % 2 == 1){
for (int i = fst; i < n; i ++){
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);
M.insert(mid);
}
}
M.erase(i);
vec[i].clear();
lst = i;
if (M.empty() or (*M.rbegin()) <= i)
break;
}
}
else{
int tmpD;
for (int i = lst; 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]);
fst = i;
if (M.empty() or *M.begin() >= i)
break;
}
}
}
for (int i : a)
Answer(i, b[hi[i]]);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |