#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
/*
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
*/
int n;
int combination[5000];
vector<int> switchstates;
vector<bool> posswitch;
vector<int> doorforswitch;
void exploreCave(int N) {
/* ... */
n=N;
switchstates.resize(n,-1);
posswitch.resize(n);
doorforswitch.resize(n);
for (int i = 0; i<n; i++){
//cout<<"door "<<i<<'\n';
//door 0
//check baseline
for (int j = 0; j<n; j++){
if (switchstates[j]==-1){
combination[j]=0;
} else {
combination[j]=switchstates[j];
}
}
for (int ix = 0; ix<n; ix++){
//cout<<switchstates[ix]<<' ';
}//cout<<'\n';
int door = tryCombination(combination);
int posfordoor = 1;
if (door==-1||door>i){
posfordoor = 0;
}
//cout<<posfordoor<<'\n';
int switchind = 0;
for (int v = 0; (1<<v)<=n; v++){
//cout<<"bit "<<v<<'\n';
//try bit i
int ptr = 0;
for (int j = 0; j<n; j++){
if (switchstates[j]==-1){
combination[j]=bool((1<<v)&ptr);
ptr++;
}
}
for (int ix = 0; ix<n; ix++){
//cout<<combination[ix]<<' ';
}//cout<<'\n';
int newdoor = tryCombination(combination);
if ((newdoor==-1||newdoor>i)==posfordoor){
switchind+=(1<<v);
}
}
//cout<<switchind<<'\n';
int ptr = 0;
for (int j = 0; j<n; j++){
if (switchstates[j]==-1){
if (ptr==switchind){
doorforswitch[j]=i;
posswitch[j]=posfordoor;
switchstates[j]=posfordoor;
break;
}
ptr++;
}
}
}
int s[5000],d[5000];
for (int i = 0; i<n; i++){
s[i]=posswitch[i];
d[i]=doorforswitch[i];
}
answer(s,d);
}
