// SB Solution
#include "cave.h"
#define N 5000
int n;
int S[N], out1[N], out2[N];
bool check[N];
void exploreCave(int _n) {
int try_num, ans, l, r, mid;
n = _n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
if (!check[j]) S[j] = 0;
try_num = tryCombination(S);
ans = try_num == i ? 1 : 0; // ans일 때 열려 있음
l = 0, r = n - 1;
while (l < r) {
mid = (l + r) / 2;
for (int j = 0; j < n; j++)
if (check[j]) continue;
else S[j] = l <= j && j <= mid ? 1 - ans : ans;
try_num = tryCombination(S);
if (try_num == i) r = mid;
else l = mid + 1;
}
S[l] = ans, check[l] = true;
out1[l] = ans, out2[l] = i;
}
answer(out1, out2);
}
