#include "cave.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <set>
using namespace std;
const int mxN = 5e3+5;
bool done[mxN];
bool open(int q, int i){
if(q == -1){
return 1;
}
return q > i;
}
void exploreCave(int N) {
int a[N], b[N];
for(int i=0; i<N; ++i){
a[i] = 0, b[i] = -1;
}
for(int i=0; i<N; ++i){
for(int j=0; j<N; ++j){
if(b[j] == -1){
a[j] = 0;
}
}
bool p = 1;
if(open(tryCombination(a), i)){
p = !p;
}
int l = 0, r = N-1, ans = -1;
while(l <= r){
int mid = (l+r)/2;
for(int j=0; j<N; ++j){
if(b[j] == -1){
if(j >= l && j <= mid){
a[j] = p;
} else {
a[j] = !p;
}
}
}
if(open(tryCombination(a), i)){
ans = mid;
r = mid-1;
} else {
l = mid+1;
}
}
assert(ans != -1);
b[ans] = i;
a[i] = p;
}
answer(a, b);
}
