#include "cave.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rt insert
#define st first
#define nd second
#define ll long long
#define DB printf("debug\n");
using namespace std;
int n;
vector < pair<int,int> > sw_st(5000);//sw i 1 -> st kapi nd state
vector < int > sw_nf;
int last_try[5000];
int new_try[5000];
int last_try_ret;
int new_try_ret;
int last_try_state;
int new_try_state;
void try_dr(int dr){
if(dr==0){
memset(last_try,0,sizeof(last_try));
memset(new_try,0,sizeof(new_try));
}
last_try_ret=tryCombination(last_try);
last_try_state= (last_try_ret>dr || last_try_ret==-1) ? 0 : 1;
//printf("1:dr = %d drst=%d ltr=%d\n",dr,last_try_state,last_try_ret);
int l=0,r=sw_nf.size()-1,m;
while(l<r){
for(int i=0;i<n;i++){
if(sw_st[i].nd==0){
new_try[i]=1;
//printf("new_try[%d]=%d\n",i,new_try[i]);
}
else if(sw_st[i].nd==1){
new_try[i]=0;
//printf("new_try[%d]=%d\n",i,new_try[i]);
}
}
m=(l+r)/2;
//printf(" dr =%d l=%d r=%d m=%d\n",dr,l,r,m);
for(int i=l;i<=m;i++){
new_try[sw_nf[i]]=!last_try[sw_nf[i]];
//printf(" new_try[%d]=%d\n",sw_nf[i],new_try[sw_nf[i]]);
}
new_try_ret=tryCombination(new_try);
new_try_state=(new_try_ret>dr || new_try_ret==-1) ? 0 : 1;
if(last_try_state!=new_try_state){
r=m;
}
else{
l=m+1;
}
//printf(" dr=%d ret=%d kon eden l=%d r=%d\n",dr,new_try_ret,l,r);
last_try_ret=new_try_ret;
last_try_state=new_try_state;
for(int i=0;i<n;i++){
last_try[i]=new_try[i];
}
}
int sw=sw_nf[l];
//printf("2:sw=%d ltr=%d lts=%d\n",sw,last_try_ret,last_try_state);
if(dr==last_try_ret){
last_try[sw]=!last_try[sw];
}
if(last_try[sw]==1){
sw_st[sw]=mp(dr,0);
}
else sw_st[sw]=mp(dr,1);
//printf("3:sw=%d st=%d dr=%d st=%d\n",sw,1,dr,sw_st[sw].nd);
sw_nf.erase(sw_nf.begin()+l);
}
void exploreCave(int N) {
n=N;
for(int i=0;i<n;i++){
sw_nf.pb(i);//bilinmeyenlere ekle
sw_st[i]=mp(-1,-1);
}
for(int i=0;i<n;i++){
try_dr(i);
}
int ans1[n],ans2[n];
for(int i=0;i<n;i++){
if(sw_st[i].nd==0)ans1[i]=1;
else ans1[i]=0;
ans2[i]=sw_st[i].st;
}
answer(ans1,ans2);
}
