#include "minerals.h"
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
void Solve(int n) {
int pr = Query(1);
std::vector<int> set1 = {1}, set2;
for (int i = 2; i <= 2 * n; ++i) {
int ne = Query(i);
(pr != ne ? set1 : set2).push_back(i);
pr = ne;
}
std::random_device rd;
std::mt19937 rng(rd());
std::shuffle(set2.begin(), set2.end(), rng);
// before dnc: set1 == set2
// make dnc step make it so
// set1 left half == set2 left half (then set1 right half is automatically ==
// set2 right half)
int saved=0;
auto solve = [&](auto &&self, int l, int r, bool added) {
if (l == r) {
Answer(set1[l], set2[l]);
return;
}
int m = l + (r - l) * 0.38;
// add/remove to/from machine
for (int i = l; i <= m; ++i) {
pr = Query(set1[i]);
}
int trues = 0, falses = 0;
std::partition(set2.begin() + l, set2.begin() + r + 1, [&](int x) {
if (falses >= r - m) {
saved++;
trues++;
return true;
}
if (trues >= m - l + 1) {
saved++;
falses++;
return false;
}
int ne = Query(x);
bool unchanged = pr == ne;
if (added) {
unchanged = !unchanged; // we actually want it to be changed
}
pr = ne;
trues += unchanged;
falses += !unchanged;
return unchanged;
});
// do dnc
self(self, l, m, !added);
self(self, m + 1, r, added);
};
solve(solve, 0, n - 1, true);
}
