#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
// int n=1,tot;
// int S[]={0};
// int D[]={0};
// int F[]={0};
// int tryCombination(int s[]){
// for(int i=0; i<n; i++){
// F[D[i]]=i;
// }
// tot++;
// int ac=0;
// for(int i=0; i<n; i++){
// if(s[F[i]]==S[F[i]])ac++;
// else break;
// }
// return ac;
// }
// void answer(int s[], int d[]){
// cout<<"try: \n";
// for(int i=0; i<n; i++)cout<<s[i]<<' ';cout<<'\n';
// for(int i=0; i<n; i++)cout<<S[i]<<' ';cout<<'\n';
// cout<<endl;
// cout<<"try: \n";
// for(int i=0; i<n; i++)cout<<d[i]<<' ';cout<<'\n';
// for(int i=0; i<n; i++)cout<<D[i]<<' ';cout<<'\n';
// if(tryCombination(s)==n)cout<<"YES";
// else cout<<"NO";
// cout<<endl<<tot;
// }
void exploreCave(int N) {
int d[N]={},s[N]={};
bool dn[N]={};
if(N==1){
if(tryCombination(s)!=1)s[0]=1;
answer(s,d);
return;
}
int ts=tryCombination(s),ts2;
for(int i=0; i<N; i++){
int l=0,r=N-1;
while(l<=r){
if(l==r){
cout<<"FOUND "<<i<<" in "<<l<<endl;
dn[l]=1;
d[l]=i;
// s[l]^=1;
if(ts2<=i)s[l]^=1;
ts=tryCombination(s);
break;
}
int md=(l+r)/2;
for(int j=l; j<=md; j++){
if(dn[j])continue;
s[j]^=1;
}
ts2=tryCombination(s);
// cout<<ts<<" # "<<l<<' '<<md<<' '<<r<<" !! ";for(int i=0; i<N; cout<<s[i++]<<' ');cout<<"!! "<<ts2<<endl;
// for(int j=l; j<=md; j++){
// if(dn[j])continue;
// s[j]^=1;
// }
if((ts<=i && ts2>=i+1) || (ts>=i+1 && ts2<=i)){
r=md;
ts=ts2;
}
else{
l=md+1;
}
}
}
answer(s,d);
}
// signed main(){
// // n=10;
// exploreCave(n);
// }
