#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int s[5005], d[5005], temp[5005];
int N;
void flip(int l, int r){
for(int i=l;i<=r;i++){
if(d[i]==-1)s[i]=!s[i];
}
}
int submit(){
//~ for(int i=0;i<N;i++){
//~ cout<<s[i]<<" ";
//~ }
int ret=tryCombination(s);
if(ret==-1)ret=N;
//~ cout<<" gives "<<ret<<endl;
return ret;
}
void exploreCave(int n) {
N=n;
//~ fill(s, s+5005, -1);
fill(d, d+5005, -1);
for(int t=0;t<n;t++){
int l=-1, r=n-1, m;
int bef=submit();
assert(bef >= t);
while(r-l>1){
m=(l+r)/2;
//~ printf("l %d r %d m %d\n", l,r,m);
flip(0, m);
int ret=submit();
assert(ret >= t);
if(bef > t){
if(ret == t){
r=m;
}
else l=m;
}
else {
if(ret > t){
r=m;
}
else l=m;
}
flip(0, m);
}
assert(d[r]==-1);
if(bef==t)flip(r, r);
d[r]=t;
}
//~ for(int i=0;i<n;i++){
//~ cout<<s[i]<<" ";
//~ }
//~ cout<<endl;
//~ for(int i=0;i<n;i++){
//~ cout<<d[i]<<" ";
//~ }
//~ cout<<endl;
answer(s, d);
}
