#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
void exploreCave(int N) {
int S[N] , D[N] , W[N];
memset(S , 0 , sizeof(S));
memset(W , 0 , sizeof(W));
int u;
while(true){
u = tryCombination(W);
if(u == -1){
break;
}
vector<int> v;
for(int i = 0;i < N;i ++){
if(W[i] == 0){
v.emplace_back(i);
}
}
auto assign = [&](vector<int> &a){
if(a.empty()){
return false;
}
for(int x : a){
W[x] = 1;
}
int A = tryCombination(W);
for(int x : a){
W[x] = 0;
}
return (A != u);
};
function<int(vector<int>&)> solve = [&](vector<int> &a){
if((int)a.size() == 1){
return a[0];
}
vector<int> L , R;
for(int i = 0;i < (int)a.size();i ++){
if(i < (int)a.size() / 2){
L.push_back(a[i]);
}else{
R.push_back(a[i]);
}
}
if(assign(L)){
return solve(L);
}
return solve(R);
};
int p = solve(v);
S[p] = W[p] = 1;
D[p] = u;
}
for(int i = 0;i < N;i ++){
W[i] = 1;
}
while(true){
u = tryCombination(W);
if(u == -1){
break;
}
vector<int> v;
for(int i = 0;i < N;i ++){
if(W[i] == 1 && !S[i]){
v.emplace_back(i);
}
}
auto assign = [&](vector<int> &a){
if(a.empty()){
return false;
}
for(int x : a){
W[x] = 0;
}
int A = tryCombination(W);
for(int x : a){
W[x] = 1;
}
return (A != u);
};
function<int(vector<int>&)> solve = [&](vector<int> &a){
if((int)a.size() == 1){
return a[0];
}
vector<int> L , R;
for(int i = 0;i < (int)a.size();i ++){
if(i < (int)a.size() / 2){
L.push_back(a[i]);
}else{
R.push_back(a[i]);
}
}
if(assign(L)){
return solve(L);
}
return solve(R);
};
int p = solve(v);
S[p] = W[p] = 0;
D[p] = u;
}
answer(S , D);
return;
}
