#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int ask(string str)
{
int *s = new int[str.size()];
for(int i = 0; i < str.size(); i++) s[i] = str[i] - '0';
int ans = tryCombination(s);
delete s; //Prevent memory leak
return ans;
}
void exploreCave(int n) {
string cur = "";
for(int i = 1; i <= n; i++) cur += "0";
set<int> st;
for(int i = 0; i < n; i++) st.insert(i);
vector<int> anss(n), ansd(n);
for(int i = 0; i < n; i++){
for(int j : st) cur[j] = '1';
int x = ask(cur), target = -1;
if(x == i) target = 0;
else target = 1;
vector<int> candidate;
for(int j : st) candidate.push_back(j);
while(candidate.size() > 1){
vector<int> le, ri;
for(int j = 0; j < candidate.size(); j++){
if(j < candidate.size()/2) le.push_back(candidate[j]);
else ri.push_back(candidate[j]);
}
for(int j : le) cur[j] = target + '0';
for(int j : ri) cur[j] = (target^1) + '0';
x = ask(cur);
if(x == i) candidate = ri;
else candidate = le;
}
int p = candidate[0];
st.erase(p);
anss[p] = target; ansd[p] = i; cur[p] = target + '0';
}
int *s = new int[n];
int *d = new int[n];
for(int i = 0; i < n; i++){s[i] = anss[i]; d[i] = ansd[i];}
answer(s, d);
}
