#include "cave.h"
#include <bits/stdc++.h>
int n;
int pos[5000];
int door[5000];
int dnc(int l, int r, bool b, int target){
if(l == r)
return l;
int mid = (l + r) >> 1;
// first check if it's in [l, mid]
int s[n];
for(int i = 0; i < n; i++){
if(pos[i] != -1){
s[i] = pos[i];
}
else if(l <= i && i <= mid){
s[i] = b;
}
else{
s[i] = !b;
}
}
int res = tryCombination(s);
if(res <= target && res != -1){
return dnc(mid + 1, r, b, target);
}
return dnc(l, mid, b, target);
}
void exploreCave(int N) {
n = N;
memset(pos, -1, sizeof(pos));
for(int i = 0; i < n; i++){
int s[n];
for(int j = 0; j < n; j++){
if(pos[j] != -1)s[j] = pos[j];
else s[j] = 0;
}
int res = tryCombination(s);
bool b = 0;
if(res <= i && res != -1){
b = 1;
}
int sw = dnc(0, n-1, b, i);
pos[sw] = b;
door[sw] = i;
}
answer(pos, door);
}
