// include
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
// random
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// templates
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (y > x) {
x = y;
return (true);
} else return (false);
}
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (y < x) {
x = y;
return (true);
} else return (false);
}
// define
#define fi first
#define se second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define eb emplace_back
#define upb upper_bound
#define lwb lower_bound
#define left VAN
#define right TAN
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).begin(),(a).end()
#define sort_and_unique(a) sort(all(a));(a).resize(unique(all(a))-a.begin())
#define max_ max_element
#define min_ min_element
// another define
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
// limit
const int oo = 2e9;
// function
void yesno(bool x) {
cout << (x ? "YES\n" : "NO\n");
}
void exploreCave(int N) {
int S[N], D[N], done[N], out[N];
for (int i = 0; i < N; i++)
S[i] = D[i] = done[i] = out[i] = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
if (!done[j])
out[j] = 0;
int ask = tryCombination(out);
int stt;
if (ask > i || ask == -1)
stt = 0;
else stt = 1;
int l = 0, r = N - 1;
while (l <= r) {
int mid = (l + r) >> 1;
for (int j = 0; j < N; j++)
if (!done[j])
out[j] = (stt ^ 1);
for (int j = l; j <= mid; j++)
if (!done[j])
out[j] = stt;
int taken = tryCombination(out);
if (taken > i || taken == -1)
r = mid - 1;
else l = mid + 1;
}
D[l] = i;
S[l] = stt;
out[l] = stt;
done[l] = 1;
}
answer(S, D);
}
