#include<bits/stdc++.h>
using namespace std;
#include "cave.h"
#define pr(x) cout<<#x<<" "<<x<<endl;
void exploreCave(int n) {
int used[n]={}, correct[n] = {};
int aa[n];
for(int i=0;i<n;i++){
// Find correct position of switch
int curr[n];
for(int j=0;j<n;j++){
if(used[j]) curr[j] = correct[j];
else curr[j] = 1;
//cout<<curr[j]<<" ";
}
//cout<<endl;
int ans = tryCombination(curr);
int correctVal = 1;
//cout<<ans<<endl;
if(ans<=i && ans!=-1) correctVal = 0;
//pr(correctVal);
// Find switch needed
int l=0, r=n-1;
int m;
while(l<=r){
m = (l+r)/2;
//cout<<m<<": ";
for(int j=0;j<=m;j++){
if(used[j]) curr[j] = correct[j];
else curr[j] = correctVal;
//cout<<curr[j]<<" ";
}
for(int j=m+1;j<n;j++){
if(used[j]) curr[j] = correct[j];
else curr[j] = 1 - correctVal;
//cout<<curr[j]<<" ";
}
//cout<<endl;
ans = tryCombination(curr);
if(ans>i || ans==-1){
r = m-1;
}
else m++, l = m;
}
used[m] = true;
correct[m] = correctVal;
aa[m] = i;
//pr(m);
//cout<<"--------------------\n";
}
answer(correct, aa);
}
