#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;
FOR(i, 0, N-1) known[i] = false;
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;
}
/*cout << " i = " << i << " mx = " << mx << " S: ";
FOR(j, 0, N-1) cout << S[j] << " ";
cout << endl;*/
vi notKnown;
FOR(j, 0, N-1) if (!known[j]) notKnown.pb(j);
/*cout << " notKnown: ";
for (int x : notKnown) cout << x << " ";
cout << endl;*/
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, le, mid) tmpS[notKnown[j]] = !S[notKnown[j]];
int cr = tryCombination(tmpS);
//cout << " le = " << le << " ri = " << ri << " mid = " << mid << " tryComb = " << cr << endl;
if (cr == i) ri = mid;
else le = mid+1;
}
int swId = notKnown[le];
D[swId] = i;
known[swId] = true;
//cout << " swId = " << swId << endl;
}
/*cout << " returnin S: ";
FOR(i, 0, N-1) cout << S[i] << " ";
cout << endl;
cout << " returnin D: ";
FOR(i, 0, N-1) cout << D[i] << " ";
cout << endl;*/
answer(S, D);
}
