#include <bits/stdc++.h>
#include "cave.h"
#define DIM 5010
using namespace std;
int n,i,j,ans;
int v[DIM],sol[DIM],f[DIM],w[DIM];
/*void answer(int s[], int d[]){
for (int i=0;i<n;i++)
cout<<s[i]<<" ";
cout<<"\n";
for (int i=0;i<n;i++)
cout<<d[i]<<" ";
}
int tryCombination (int S[]){
int ans,i;
for (i=0;i<n;i++)
cout<<S[i]<<" ";
cout<<endl;
cin>>ans;
cout<<endl;
return ans;
}*/
int verif (int y){
for (int i=0;i<n;i++){
if (f[i]){
w[i] = v[i];
continue;
}
if (i <= y)
w[i] = 1 - v[i];
else w[i] = v[i];
}
return tryCombination(w);
}
void exploreCave (int N){
n = N;
int ok = 0;
for (i=0;i<n;i++){
int ans = tryCombination(v);
if (ans == -1)
break;
if (ans != i){
for (j=0;j<n;j++)
if (!f[j])
v[j] = 1-v[j];
}
int st = 0, dr = n-1;
while (st < dr){
int mid = (st+dr)>>1;
int ans = verif (mid);
if (ans == -1){
ok = 1;
for (j=0;j<n;j++)
v[j] = w[j];
break;
}
if (ans > i)
dr = mid;
else st = mid+1;
}
if (ok)
break;
/// st
sol[st] = i;
f[st] = 1;
v[st] = 1 - v[st];
}
for (i=0;i<n;i++){
if (f[i])
continue;
if (v[i] == 0){
v[i] = 1;
sol[i] = tryCombination(v);
v[i] = 0;
} else {
v[i] = 0;
sol[i] = tryCombination(v);
v[i] = 1;
}
}
answer(v,sol);
}
