#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define imie(...) " [" << #__VA_ARGS__ ": "<< (__VA_ARGS__) << "] "
#define ed <<endl
const int op = 1;
const int cl = 0;
void exploreCave(int n) {
int cur[n];
int fixed[n];
int mat[n];
for(int i=0;i<n;i++){
cur[i] = fixed[i] = mat[i] = 0;
}
for(int i=0;i<n;i++){
int temp = tryCombination(cur);
int st;
if(temp == -1 or temp > i){
st = op;
} else{
st = cl;
}
if(st == op){
int lo = 0;
int hi = n-1;
while(hi != lo){
int mid = lo + ((hi-lo)/2);
int me[n];
for(int j=0;j<n;j++){
me[j] = cur[j];
}
for(int j=lo;j<=mid;j++){
if(!fixed[j]){
me[j] = !cur[j];
}
}
int res = tryCombination(me);
if(res == i){
hi = mid;
} else{
lo=mid+1;
}
}
cur[hi]=0;
fixed[hi]=1;
mat[hi] = i;
} else{
int lo = 0;
int hi = n-1;
while(hi != lo){
int mid = lo + ((hi-lo)/2);
int me[n];
for(int j=0;j<n;j++){
me[j] = cur[j];
}
for(int j=lo;j<=mid;j++){
if(!fixed[j]){
me[j] = !cur[j];
}
}
int res = tryCombination(me);
if(res != i){
hi = mid;
} else{
lo=mid+1;
}
}
cur[hi]=1;
fixed[hi]=1;
mat[hi]=i;
}
}
answer(cur, mat);
}
