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