#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int MAXN = 5000;
int switch_[MAXN];
int on_off[MAXN];
int nn;
void fill(int until, int bit){
for(int i = 0;i < nn;i ++ ){
if(switch_[i] == -1){
on_off[i] = (i < until ? bit : 1 - bit);
}
}
}
void open_door(int u){
fill(nn, 1);
int tt = tryCombination(on_off);
int byt = 0;
if(tt == -1 or tt > u)
byt = 1;
int lf = 0,rf = nn + 1;
int md;
while(rf-lf>1){
md = (lf + rf) / 2;
fill(md, byt);
tt = tryCombination(on_off);
if(tt == -1 or tt > u)
rf = md;
else
lf = md;
}
switch_[rf-1] = u;
on_off[rf-1] = byt;
fill(nn,0);
}
void exploreCave(int N) {
for(int i = 0;i < MAXN;i ++ )
switch_[i] = -1, on_off[i] = -1;
nn = N;
for(int i = 0;i < nn;i ++ )
open_door(i);
answer(on_off, switch_);
}
