# include "cave.h"
# include <bits/stdc++.h>
# define FILE
using namespace std;
/*
int tryCombination( int S[] ){
return 0;
}
void answer( int S[], int D[] ){
exit( 0 );
}
*/
void exploreCave(int N){
int S[N] = {}, D[N] = {};
for( int i = 0; i < N; i ++ )
S[i] = D[i] = -1;
int loc[N] = {};
for( int i = 0; i < N; i ++ ){
for( int i = 0; i < N; i ++ ){
if( S[i] == -1 ){
loc[i] = 0;
}
else{
loc[i] = S[i];
}
}
int open = 0;
int door = tryCombination( loc );
if( door == i ){
open = 1;
for( int i = 0; i < N; i ++ ){
if( S[i] == -1 ){
loc[i] = open;
}else{
loc[i] = S[i];
}
}
}
int l = 0, r = N-1;
while( l != r ){
int m = ( l + r ) >> 1;
for( int i = l; i <= m; i ++ ){
if( S[i] == -1 ){
loc[i] = 1-open;
}else{
loc[i] = S[i];
}
}
int door = tryCombination( loc );
if( door == i ){
r = m;
}else{
l = m+1;
}
for( int i = l; i <= m; i ++ ){
if( S[i] == -1 ){
loc[i] = 1-open;
}else{
loc[i] = S[i];
}
}
}
S[l] = open;
D[i] = l;
}
answer( S, D );
}
/*
int main(){
# ifdef FILE
freopen( "input.txt", "r", stdin );
freopen( "output.txt", "w", stdout );
# endif
}
*/
