#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
#define MID ((l+r)/2)
int n;
bool used[10000000] = {};
int state[10000000] = {};
int cnt=0;
int query(int l, int r, int sttate){
if(l>=r) return l;
int a[n] = {};
for(int i=0;i<l;i++){
if(used[i]) a[i] = state[i];
else a[i] = 1-sttate;
}
for(int i=l;i<=MID;i++){
if(used[i]) a[i] = state[i];
else a[i] = sttate;
}
for(int i=MID+1;i<n;i++){
if(used[i]) a[i] = state[i];
else a[i] = 1-sttate;
}
//for(int i=0;i<n;i++) cout<<a[i]<<" ";
//cout<<endl;
//cout<<tryCombination(a)<<endl<<endl;
int cans = tryCombination(a);
if(cans<cnt && cans>=0){
return query(MID+1, r, sttate);
}
else return query(l, MID, sttate);
}
void exploreCave(int N) {
n = N;
int ans[n] = {};
for(int i=0;i<n;i++){
int a[n] = {};
for(int j=0;j<n;j++) a[j] = (used[j] ? state[j] : 0);
int correct_state = 1;
cnt = i+1;
//cout<<"============ "<<cnt<<" ==============\n";
//cout<<"STATE DET: ";
//for(int j=0;j<n;j++) cout<<a[j]<<" ";
//cout<<endl;
//cout<<tryCombination(a)<<endl<<endl;
if(tryCombination(a)>=cnt || tryCombination(a)==-1) correct_state=0;
//cout<<"STATE: "<<correct_state<<endl;
int pos = query(0, n-1, correct_state);
ans[pos] = i;
state[pos] = correct_state;
used[pos] = true;
}
answer(state, ans);
}
