// In the name of Allah
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int tryCombination(int S[]);
void answer(int S[], int D[]);
const int maxn = 5000 + 4;
int n;
int M[maxn], res[maxn];
vector<int> ls;
void exploreCave(int Nx) {
n = Nx;
for (int i = 0; i < n; i++) ls.pb(i);
for (int j = 0; j < n; j++) {
int x = tryCombination(M);
if (x == -1 || x > j) {
for (int r : ls) M[r] = (1 - M[r]);
}
int l = 0, r = len(ls);
while (r - l > 1) {
int mid = (l + r) / 2;
for (int i = 0; i < mid; i++) {
int r = ls[i];
M[r] = (1 - M[r]);
}
int x = tryCombination(M);
for (int i = 0; i < mid; i++) {
int r = ls[i];
M[r] = (1 - M[r]);
}
if (x == -1 || x > j) r = mid;
else l = mid;
}
int k = ls[l];
M[k] = (1 - M[k]); res[k] = j;
ls.erase(ls.begin() + l);
}
answer(M, res);
}
