#include <iostream>
#include <vector>
#include <unordered_set>
#include <deque>
#include "cave.h"
using namespace std;
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N){
int doors[N]={};
int perm[N] = {};
deque<int> av;
unordered_set<int> f;
int tr[N] = {};
for (int s=0; s<N; s++){
int pos = 0;
for (int i=0; i<N; i++){
if (f.count(i)) tr[i] = perm[i]; else tr[i]=0;
}
int r = tryCombination(tr);
if (r==s) pos = 1;
if (!pos) for (int i=0; i<N; i++){
if (f.count(i)) tr[i] = perm[i]; else tr[i]=1;
}
while (!av.empty()) av.pop_back();
for (int i=0; i<N; i++) if (!f.count(i)) av.push_back(i);
int a = 0, b = (int)av.size()-1;
while (a!=b){
int m = (a+b)/2;
int q = 0;
for (auto it = av.begin(); q<=m; it++){
if (!f.count(*it)) tr[*it] = pos;
q++;
}
r = tryCombination(tr);
if (r==s) {
int q = a;
for (auto it = av.begin(); q<=m; it++){
if (!f.count(*it)) tr[*it] =! pos;
q++;
}
for (int i=a; i<=m; i++) av.pop_front();
a = m+1;
}else {
int q = a;
for (auto it = av.begin(); q<=m; it++){
if (!f.count(*it)) tr[*it] = !pos;
q++;
}
for (int i=b; i>m; i--) av.pop_back();
b =m;
}
}
doors[av.front()] = s;
perm[av.front()] = pos;
f.insert(av.front());
tr[av.front()] = pos;
}
answer(perm,doors);
}
