#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int s[6000];
int d[6000];
int used[6000];
int n, color;
int check(int l, int r){
int i;
for(i=0;i<n;i++){
if(used[i] == 1)continue;
s[i] = 0;
}for(i=l;i<=r;i++){
if(used[i] == 1)continue;
s[i] = 1;
}
return tryCombination(s);
}
void exploreCave(int N) {
n = N;
for(int door = 0; door < n; door ++){
color = tryCombination(s);
if(color == -1){
color = n;
}if(color >= door+1)color = 0;
else color = 1;
int l=0, r=n-1;
while(l < r){
int mid = (l+r)/2;
int ch = check(l, mid);
if(((color == 1)^(ch == door))){
r = mid;
}else {
l = mid+1;
}
}//cout << l << '\n';
used[l] = 1;
s[l] = color;
d[l] = door;
for(int i=0;i<n;i++){
if(used[i])continue;
s[i] = 0;
}
}
answer(s, d);
}
/*
4
1 1 1 0
3 1 0 2
*/
