#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int recurse(vector<int>& guess,int pos,const vector<int>& door,const vector<int>& setting,int l,int r,int N) //in [l,r)
{
if(r-l==1) return l;
int mid=l+(r-l)/2;
fill(guess.begin()+l,guess.begin()+mid,1);
for(int i=0;i<N;i++)
{
if(door[i]!=-1)
{
guess[door[i]]=setting[i];
}
}
int next=tryCombination(guess.data());
if(next==pos)
{
if(setting[pos]==0)
{
fill(guess.begin()+l,guess.begin()+mid,0);
return recurse(guess,pos,door,setting,l,mid,N);
}else
{
return recurse(guess,pos,door,setting,mid,r,N);
}
}else
{
if(setting[pos]==0)
{
return recurse(guess,pos,door,setting,mid,r,N);
}else
{
fill(guess.begin()+l,guess.begin()+mid,0);
return recurse(guess,pos,door,setting,l,mid,N);
}
}
}
void exploreCave(int N) {
vector<int> door(N,-1),setting(N,-1);
for(int i=0;i<N;i++)
{
vector<int> guess(N);
fill(guess.begin(),guess.end(),0);
for(int i=0;i<N;i++)
{
if(door[i]!=-1)
{
guess[door[i]]=setting[i];
}
}
//for(auto& e:guess) cout<<e<<" ";
//cout<<endl;
int next=tryCombination(guess.data());
//cout<<i<<" "<<next<<endl;
setting[i]=(next==i);
door[i]=recurse(guess,i,door,setting,0,N,N);
}
vector<int> invdoor(N),invset(N);
for(int i=0;i<N;i++)
{
invdoor[door[i]]=i;
invset[door[i]]=setting[i];
}
answer(invset.data(),invdoor.data());
}
