#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[400000];
ll sz, z;
random_device rd;
ll query(ll u) {
B[u] ^= 1;
return Query(u);
}
mt19937 mt(rd());
void solve(ll id, ll l, ll r) {
if (l == r) {
Answer(X[l], st[id][0]);
return;
}
ll mid = (l+r)/2, 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;
}
if (l == mid) {
Answer(X[l], st[id*2][0]);
}
else {
ll xm = (l+mid)/2;
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]);
return;
}
ll xm = (mid+1+r)/2;
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;
ll tot = N;
vector <ll> V;
for (int i=1; i<=2*N; ++i) {
V.push_back(i);
}
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=(N-1)/2+1; i<N; ++i) sz = query(X[i]);
solve(1, 0, tot-1);
}
Compilation message
minerals.cpp: In function 'void solve(long long int, long long int, long long int)':
minerals.cpp:25:3: error: 'shuffle' was not declared in this scope
25 | shuffle(st[id].begin(), st[id].end(), mt);
| ^~~~~~~
minerals.cpp:54:3: error: 'sort' was not declared in this scope; did you mean 'qsort'?
54 | 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:78:3: error: 'shuffle' was not declared in this scope
78 | shuffle(X.begin(), X.end(), mt);
| ^~~~~~~
