#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> A;
int solve(int N, int M, int st, vector<int> S) {
if (S.size() == 1) return S[0];
int K = S.size();
int T[N];
for (int i = 0; i < N; i++) {
if (A[i] != -1) T[i] = A[i];
else T[i] = !st;
}
for (int i = 0; i < K/2; i++) T[S[i]] = st;
vector<int> nw;
int res = tryCombination(T), L = K / 2, R = K;
if (res > M || res == -1) L = 0, R = K / 2;
for (int i = L; i < R; i++) nw.emplace_back(S[i]);
return solve(N, M, st, nw);
}
void exploreCave(int N) {
for (int i = 0; i < N; i++) A.emplace_back(-1);
int D[N];
for (int M = 0; M < N; M++) {
vector<int> S;
int T[N];
for (int i = 0; i < N; i++) if (A[i] == -1) S.emplace_back(i);
for (int i = 0; i < N; i++) T[i] = (A[i] != -1) * A[i];
int res = tryCombination(T), t = !(res > M || res == -1);
int ans = solve(N, M, t, S);
A[ans] = t, D[M] = ans;
}
int S[N];
for (int i = 0; i < N; i++) S[i] = A[i];
answer(S, D);
}
