#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
typedef vector<ll> vl;
void exploreCave(int N) {
int S[N];
int D[N];
bool known[N];
FOR(i, 0, N-1) S[i] = 0, D[i] = i;
int mx = tryCombination(S);
if (mx == -1) mx = N;
FOR(i, 0, N-1) {
if (mx == i) {
FOR(j, 0, N-1) if (!known[j]) S[j] = !S[j];
mx = tryCombination(S);
if(mx==-1) mx = N;
}
vi notKnown;
FOR(j, 0, N-1) if (!known[j]) notKnown.pb(j);
int le = 0, ri = (int)notKnown.size()-1;
while (le < ri) {
int mid= (le+ri)/2;
int tmpS[N];
FOR(j, 0, N-1) tmpS[j] = S[j];
FOR(j, 0, mid) tmpS[notKnown[j]] = !S[notKnown[j]];
int cr = tryCombination(tmpS);
if (cr == i) ri = mid;
else le = mid+1;
}
int swId = le;
D[swId] = i;
known[swId] = true;
}
answer(S, D);
}
