#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
int n=N;
int R[n+10];int P[n+10];
int aux2[n+10];
int x,y;
bool z;
for(int i=0;i<n;i++){
R[i]=1;
P[i]=-1;
}
for(int i=0;i<n;i++){
for(int l=0;l<n;l++){aux2[l]=R[l];}
int p1=0,p2=n-1;
x=tryCombination(aux2);z=1;
while(abs(p1-p2)!=1){
int p3=(p1+p2)/2;
if(z){
for(int l=p1;l<=p3;l++){
if(P[l]==-1){
aux2[l]=0;
}
}}else{
for(int l=p1;l<=p3;l++){
if(P[l]==-1){
aux2[l]=1;
}
}
}
y=tryCombination(aux2);
if((x>=i+1 || x==-1) && (y>=i+1 || y==-1)){p1=p3+1;z=0;}
else if((x>=i+1 || x==-1) && (y<i+1 && y!=-1)){p2=p3;z=1;}
else if((x<i+1 && x!=-1) && (y>=i+1 || y==-1)){
p2=p3;
z=1;
}
else if((x<i+1 && x!=-1) && (y<i+1 && y!=-1)){
p1=p3+1;
z=0;
}
x=y;
}
if(aux2[p1]==1 && P[p1]==-1){aux2[p1]=0;}
else if(aux2[p1]==0 && P[p1]==-1){aux2[p1]=1;}
y=tryCombination(aux2);
if((x>=i+1 || x==-1) && (y>=i+1 || y==-1)){R[p2]=aux2[p2];P[p2]=i;}
else if((x<i+1 && x!=-1) && (y>=i+1 || y==-1)){R[p1]=aux2[p1];P[p1]=i;}
else if((x>=i+1 || x==-1) && (y<i+1 && y!=-1)){if(aux2[p1]==1){aux2[p1]=0;}
else{aux2[p1]=1;}
R[p1]=aux2[p1];P[p1]=i;
}
else if((x<i+1 && x!=-1) && (y<i+1 && y!=-1)){if(aux2[p2]==1){aux2[p2]=0;}
else{aux2[p2]=1;}
R[p2]=aux2[p2];
P[p2]=i;
}
}
answer(R,P);
}
