#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int matched[5010];
int door[5010];
int det[5010][3];
bool fp=false;
int mc=0;
void foundpath(int arr[]){
for(int i=0;i<n;i++){
if(matched[i]==-1){
matched[i]=arr[i];
arr[i]=(arr[i]+1)%2;
int val=tryCombination(arr);
door[i]=val;
arr[i]=(arr[i]+1)%2;
}
}
return;
}
void calc(int x){
if(fp==true || mc==n)return;
int a=det[x][0],b,c;
int arr[n];
while(true){
b=det[x][1],c=det[x][2];
if(b==c){
matched[b]=a;
door[b]=x;
mc++;
return;
}
for(int i=0;i<n;i++){
if(matched[i]!=-1)arr[i]=matched[i];
else arr[i]=0;
}
for(int i=b;i<=(b+c)/2;i++)if(matched[i]==-1)arr[i]=1;
int val=tryCombination(arr);
if(val==-1){
foundpath(arr);
fp=true;
return;
}
if(a==1){
if(val>x)det[x][2]=(b+c)/2;
else if(val==x)det[x][1]=(b+c)/2+1;
else {
det[val][0]=0;
det[val][1]=b;
det[val][2]=(b+c)/2;
calc(val);
}
}
else{
if(val>x)det[x][1]=(b+c)/2+1;
else if(val==x)det[x][2]=(b+c)/2;
else {
det[val][0]=1;
det[val][1]=(b+c)/2+1;
det[val][2]=c;
calc(val);
}
}
}
return;
}
void exploreCave(int N) {
n=N;
for(int i=0;i<n;i++){
matched[i]=door[i]=-1;
det[i][0]=-1;
det[i][1]=0;det[i][2]=n-1;
}
int arr[n];memset(arr,0,sizeof(arr));
while(true){
for(int i=0;i<n;i++)if(matched[i]!=-1)arr[i]=matched[i];
int val=tryCombination(arr);
if(val==-1){foundpath(arr);break;}
det[val][0]=1;
calc(val);
}
int S[n];
int D[n];
for(int i=0;i<n;i++){S[i]=matched[i];D[i]=door[i];}
answer(S,D);
return;
}
