#include "minerals.h"
#include <iostream>
#include <vector>
#include <random>
#define ll long long
using namespace std;
vector <ll> X, Y;
bool B[100000];
vector <ll> st[1000000];
ll sz, z;
random_device rd;
ll query(ll u) {
B[u] ^= 1;
return Query(u);
}
ll M(ll l, ll r) {
if (l == r) return l;
return min(r-1, l+(r-l+1)*4/7-1);
}
mt19937 mt(rd());
void solve(ll id, ll l, ll r) {
if (l == r) {
Answer(X[l], st[id][0]);
return;
}
ll mid = M(l, r), a = 0, b = 0;
shuffle(st[id].begin(), st[id].end(), mt);
for (auto u : st[id]) {
if (a == mid-l+1) {
st[id*2+1].push_back(u);
continue;
}
else if (b == r-mid) {
st[id*2].push_back(u);
continue;
}
z = query(u);
if (sz == z) st[id*2].push_back(u), ++a;
else st[id*2+1].push_back(u), ++b;
sz = z;
}
ll xm;
if (l == mid) {
Answer(X[l], st[id*2][0]);
}
else {
xm = M(l, mid);
for (int i=l; i<=xm; ++i) if (!B[X[i]]) sz = query(X[i]);
for (int i=xm+1; i<=mid; ++i) if (B[X[i]]) sz = query(X[i]);
solve(id*2, l, mid);
}
if (mid+1 == r) {
Answer(X[r], st[id*2+1][0]);
}
else {
xm = M(mid+1, r);
sort(st[id*2+1].begin(), st[id*2+1].end(), [](auto a, auto b) {
return B[a] > B[b];
});
for (int i=mid+1; i<=r; ++i) {
swap(X[i], st[id*2+1][i-mid-1]);
}
for (int i=mid+1; i<=xm; ++i) if (!B[X[i]]) sz = query(X[i]);
for (int i=xm+1; i<=r; ++i) if (B[X[i]]) sz = query(X[i]);
solve(id*2+1, mid+1, r);
}
}
void Solve(int N) {
sz = 0;
for (int i=1; i<=2*N; ++i) {
z = query(i);
if (sz != z) X.push_back(i);
else Y.push_back(i);
sz = z;
}
shuffle(X.begin(), X.end(), mt);
shuffle(Y.begin(), Y.end(), mt);
for (auto u : Y) st[1].push_back(u);
for (int i=M(0, N-1)+1; i<N; ++i) sz = query(X[i]);
solve(1, 0, N-1);
}
Compilation message
minerals.cpp: In function 'void solve(long long int, long long int, long long int)':
minerals.cpp:29:3: error: 'shuffle' was not declared in this scope
29 | shuffle(st[id].begin(), st[id].end(), mt);
| ^~~~~~~
minerals.cpp:59:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
59 | sort(st[id*2+1].begin(), st[id*2+1].end(), [](auto a, auto b) {
| ^~~~
| qsort
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:79:3: error: 'shuffle' was not declared in this scope
79 | shuffle(X.begin(), X.end(), mt);
| ^~~~~~~
