#include "cave.h"
#include <vector>
#include <map>
#include <iostream>
using namespace std;
int d;
vector<int> cur,sp,fix;
int prv=-1;
// map<vector<int>,int> bf;
// int ASK(vector<int>& cp)
// {
// if(bf.find(cp)==bf.end())
// bf[cp]=tryCombination(cp.data());
// return bf[cp];
// }
bool ask(int l,int r)
{
for(;l<=r;l++)
if(!fix[l])
cur[l]=!cur[l];
int nc=tryCombination(cur.data());
if(prv==d and (nc>d or nc==-1))
{
prv=nc;
return 1;
}
else if((prv==-1 or prv>d) and nc==d)
{
prv=nc;
return 1;
}
for(;l<=r;l++)
if(!fix[l])
cur[l]=!cur[l];
prv=nc;
return 0;
}
void find_switch(int l,int r)
{
if(l==r)
{
fix[l]=1;
sp[l]=d;
if(prv==d)
{
cur[l]=!cur[l];
prv=tryCombination(cur.data());
}
return;
}
int mid=(l+r)/2;
if(ask(l,mid))
{
find_switch(l,mid);
}
else
{
find_switch(mid+1,r);
}
}
void exploreCave(int n)
{
cur.resize(n,0);
sp.resize(n,0);
fix.resize(n,0);
prv=tryCombination(cur.data());
for(d=0;d<n;d++)
find_switch(0,n-1);
answer(cur.data(),sp.data());
}
