#include <bits/stdc++.h>
#include "cave.h"
// #include "grader.h"
using namespace std;
using ll = long long;
ll n, m, q, k, x, y, a, b, c;
ll func(set<int> &st, int *v, int open, int x) {
// for (auto i : st) {
// cout << i << ' ';
// }
// cout << '\n';
// cout << '\t' << open << '\n';
if (st.size() == 1) {
return *st.begin();
}
ll sz = st.size() / 2;
set<int> st1, st2;
for (int i = 0; i < sz; i++) {
st1.insert(*st.begin());
st.erase(st.begin());
}
while (st.size() > 0) {
st2.insert(*st.begin());
st.erase(st.begin());
}
for (auto i : st1) {
v[i] = open;
}
bool fl = 0;
// for (int j = 0; j < n; j++) {
// cout << v[j] << ' ';
// }
// cout << '\n';
ll tr = tryCombination(v);
// cout << '\t' << tr << '\n';
if (tr == x) {
fl = 1;
}
for (auto i : st1) {
v[i] = 1 - open;
}
if (fl) {
swap(st1, st2);
}
// cout << '\n';
return func(st1, v, open, x);
}
void exploreCave(int N) {
n = N;
int *ans1 = new int[n];
int *ans2 = new int[n];
set<int> st;
for (int i = 0; i < n; i++) {
st.insert(i);
}
vector<bool> open(n);
vector<int> point(n, -1);
int *v = new int[n];
for (int i = 0; i < n; i++) {
// cout << i << endl;
for (int j = 0; j < n; j++) {
v[j] = 0;
}
for (int j = 0; j < n; j++) {
if (point[j] != -1) {
v[point[j]] = open[j];
}
}
// for (int j = 0; j < n; j++) {
// cout << v[j] << ' ';
// }
// cout << '\n';
ll tr = tryCombination(v);
// cout << '\t' << tr << '\n';
if (tr == i) {
open[i] = 1;
}
else {
open[i] = 0;
}
for (auto j : st) {
v[j] = 1 - open[i];
}
set<int> st1 = st;
ll x = func(st1, v, open[i], i);
point[i] = x;
st.erase(x);
}
// for (int i = 0; i < n; i++) {
// cout << open[i] << ' ' << point[i] << '\n';
// }
// cout << '\n';
for (int i = 0; i < n; i++) {
ans2[point[i]] = i;
ans1[point[i]] = open[i];
}
// for (int i = 0; i < n; i++) {
// cout << ans1[i] << ' ' << ans2[i] << '\n';
// }
answer(ans1, ans2);
}
