#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ff first
#define ss second
#define ln "\n"
ll n;
ll S[5000], D[5000];
ll ar[5000];
ll excl[5000];
ll ask(ll ind){
for (ll i=0; i<n; i++) {
if (excl[i]) ar[i]=S[i];
else ar[i]=0;
}
for (ll i=0; i<=ind; i++){
if (excl[i]) continue;
else ar[i]=1;
}
// for (ll i=0; i<n; i++) cout << ar[i] << " ";
// cout << " :: " << tryCombination(ar) << ln;
return tryCombination(ar);
}
void exploreCave(int N) {
n=N;
memset(S, 0, sizeof S); memset(D, 0, sizeof D);
memset(excl, 0, sizeof excl);
ll ind=tryCombination(S);
for (ll i=0; i<N; i++){
ll l=-1, r=N-1;
while (l+1<r){
ll mid = (l+r)/2;
ll ret=ask(mid);
if ((ind==i and ret!=i) or (ind!=i and ret==i)) r=mid;
else l=mid;
}
// cout << ind << ":" << r << ln;
if (ind==i) S[r]=1;
else S[r]=0;
D[r]=i;
excl[r]=1;
ind=tryCombination(S);
}
answer(S, D);
}
