#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
const int MOD = 1e9+7; // 998244353;
void exploreCave(int n) {
int a[n];
int b[n];
for (int i = 0; i < n; ++i) {
a[i] = -1;
}
for (int i = 0; i < n; ++i) {
vctr<int> v;
for (int j = 0; j < n; ++j) {
if (a[j] != -1)continue;
v.pb(j);
}
// vdbg(v);
bool o = false;
{
int d[n];
for (int j = 0; j < n; ++j) {
if (a[j] != -1)d[j] = a[j];
else d[j] = 0;
}
int res = tryCombination(d);
// adbg0(d,n);
// dbg(res);
o = (res == -1 || res > i);
}
int l = 0, r = (int)v.size()-1;
while (l < r) {
int m = l+(r-l)/2;
int d[n];
for (int j = 0; j < n; ++j) {
if (a[j] != -1)d[j] = a[j];
else d[j] = (j <= v[m] ? 1 : 0);
}
int res = tryCombination(d);
// adbg0(d,n);
// dbg(res);
if (o^(res == -1 || res > i)) {
r = m;
} else {
l = m+1;
}
}
// dbg(v[l]);
a[v[l]] = !o;
b[v[l]] = i;
}
answer(a,b);
return;
}
