#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
#endif
//#define int long long
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vb vector<bool>
#define vvb vector<vb>
#define endl '\n'
#define sp <<' '<<
#define F(i, s, n) for(int i = s; i < (int) n; i++)
#define pb push_back
#define fi first
#define se second
const int mod = 998244353;
const int inf = 1e12;
const int N = 2e5+5;
void exploreCave(int32_t n) {
int found[n];
int connected[n];
F(i, 0, n) found[i] = -1;
F(di, 0, n) {
int allZero[n];
F(i, 0, n) if(found[i] != -1) {
allZero[i] = found[i];
} else {
allZero[i] = 0;
}
int initial = tryCombination(allZero);
deque<int> possible;
F(i, di+1, n) if(found[i] == -1) possible.pb(i);
while(possible.size() > 1) {
int m = possible.size() >> 1;
int toTry[n];
F(i, 0, n) if(found[i] != -1) {
toTry[i] = found[i];
}
F(i, 0, m) toTry[possible[i]] = 1;
int ret = tryCombination(toTry);
if(ret != initial) { // the door was alternated
int ps = possible.size();
F(i, m, ps) possible.pop_back();
} else {
F(i, 0, m) possible.pop_front();
}
}
found[possible[0]] = (initial == di);
connected[possible[0]] = di;
}
answer(found, connected);
}
