#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5000 + 7;
int state[N];
int inv[N];
int guy[N];
void exploreCave(int n) {
/**
int S[] = {1, 1, 1, 0};
int D[] = {3, 1, 0, 2};
answer(S, D);
**/
vector<int> guys(n);
iota(guys.begin(), guys.end(), 0);
for (int pos = 0; pos < n; pos++) {
int tl = 0, tr = (int) guys.size() - 1;
while (tl < tr) {
int tm = (tl + tr) / 2;
vector<int> my_part;
for (int j = tl; j <= tm; j++) {
my_part.push_back(guys[j]);
}
int sol1 = tryCombination(state);
if (sol1 == -1) sol1 = n;
for (auto &x : my_part) state[x] ^= 1;
int sol2 = tryCombination(state);
if (sol2 == -1) sol2 = n;
for (auto &x : my_part) state[x] ^= 1;
bool ok1 = (sol1 >= pos + 1);
bool ok2 = (sol2 >= pos + 1);
if (ok1 == ok2) {
tl = tm + 1;
} else {
tr = tm;
}
}
int sol = tryCombination(state);
if (sol == -1) sol = n;
if (sol < pos + 1) {
state[guys[tl]] ^= 1;
}
sol = tryCombination(state); /// this is pretty much just for assertion
if (sol == -1) sol = n;
assert(sol >= pos + 1);
inv[guys[tl]] = pos;
vector<int> pguys;
for (int j = 0; j < (int) guys.size(); j++) {
if (j != tl) {
pguys.push_back(guys[j]);
}
}
guys = pguys;
}
answer(state, inv);
}
