#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
///Binary Search
///Greedy
///Find the position and correct states of the switches
#define debug(x) cout<<#x<<" = "<<x<<endl
int correct[5005];
int pos[5005];
int A[5005];
int locked[5005];
void Init(int n)
{
for(int i=0;i<n;i++){
A[i]=(locked[i]==-1)? 0 : locked[i];
}
}
void findPosition(int id,int n)
{
int L=0,R=n-1;
while(L<R){
int mid=(L+R)/2;
if(correct[id]==0){
for(int i=L;i<mid+1;i++){
A[i]=(locked[i]==-1)? 0 : locked[i];
}
for(int i=mid+1;i<=R;i++){
A[i]=(locked[i]==-1)? 1 : locked[i];
}
}
else{
for(int i=L;i<mid+1;i++){
A[i]=(locked[i]==-1)? 1 : locked[i];
}
for(int i=mid+1;i<=R;i++){
A[i]=(locked[i]==-1)? 0 : locked[i];
}
}
if(tryCombination(A)!=id)
R=mid;
else
L=mid+1;
}
pos[L]=id;
locked[L]=correct[id];
}
void exploreCave(int n) {
memset(locked,-1,sizeof locked);
for(int i=0;i<n;i++){
Init(n);
if(tryCombination(A)!=i)
correct[i]=0;
else
correct[i]=1;
findPosition(i,n);
}
answer(locked,pos);
}
