#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int A[5005], B[5005], C[5005];
bool F[5005];
vector<int> V;
// yeet
void exploreCave(int N) {
for (int i = 0; i < N; i++) V.push_back(i);
for (int i = 0; i < N; i++) {
int lo = 0, hi = V.size() - 1;
bool st = tryCombination(A) == i;
while (lo < hi) {
int mid = (lo + hi) / 2;
for (int i = lo; i <= mid; i++)
A[V[i]] = !A[V[i]];
bool nst = tryCombination(A) == i;
if (nst != st) st = nst, hi = mid;
else lo = mid + 1;
}
if (st) C[V[lo]] = A[V[lo]];
else C[V[lo]] = !A[V[lo]];
A[V[lo]] = !C[V[lo]];
B[V[lo]] = i;
F[V[lo]] = 1;
V.clear();
for (int i = 0; i < N; i++)
if (!F[i]) V.push_back(i);
}
answer(A, B);
}
// yeet
