#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
// #define F first
// #define S second
#include "cave.h"
int N;
int S[5005], D[5005], C[5005], DTI[5005];
void skibidi(int d) {
FOR(i, N) C[i] = 0;
FOR(i, d) C[DTI[i]] = S[DTI[i]];
int s;
if (tryCombination(C) == d) s = 1;
else s = 0;
int l = 0, r = N;
while(l < r - 1) {
int m = (l + r) / 2;
FOR(i, N) C[i] = s;
for(int i = l; i < m; i++) C[i] = 1-s;
FOR(i, d) C[DTI[i]] = S[DTI[i]];
if (tryCombination(C) == d) {
r = m;
} else {
l = m;
}
}
S[l] = s;
D[l] = d;
DTI[d] = l; // door to index [in S]
}
void exploreCave(int N) {
::N = N;
FOR(door, N) skibidi(door);
answer(S, D);
}
// signed main() {
// cin.tie(0); ios::sync_with_stdio(false);
// }
