#include "cave.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
typedef long long llong;
const int MAXN = 5000 + 10;
const int INF = 1e9;
int ans[MAXN];
int con[MAXN];
int val[MAXN];
int guess[MAXN];
std::vector <int> switchs;
void exploreCave(int n)
{
switchs.resize(n);
std::iota(switchs.begin(), switchs.end(), 0);
for (int i = 0 ; i < n ; ++i)
{
int setTo = 1;
std::fill(guess, guess + n, 1);
for (int j = 0 ; j < i ; ++j)
{
guess[ans[j]] = val[ans[j]];
}
int res = tryCombination(guess);
if (res == i)
{
setTo = 0;
}
int l = -1, r = switchs.size() - 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
std::fill(guess, guess + n, setTo ^ 1);
for (int j = 0 ; j < i ; ++j)
{
guess[ans[j]] = val[ans[j]];
}
for (int j = 0 ; j <= mid ; ++j)
{
guess[switchs[j]] = setTo;
}
res = tryCombination(guess);
if (res == i) l = mid;
else r = mid;
}
ans[i] = switchs[r];
val[switchs[r]] = setTo;
switchs.erase(switchs.begin() + r);
}
for (int i = 0 ; i < n ; ++i)
{
con[ans[i]] = i;
}
answer(val, con);
}
