#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
vector<int> S(N, 0); // 最終答案：每個 switch 的狀態
vector<int> D(N, -1); // 最終答案：switch -> door
vector<int> used(N, 0); // 該 switch 是否已經被確定
for (int i = 0; i < N; i++) {
vector<int> cur(N, 0);
// 已經確定的 switch 固定
for (int j = 0; j < N; j++) {
if (used[j]) cur[j] = S[j];
else cur[j] = 0;
}
int base = tryCombination(cur.data());
int L = 0, R = N - 1;
while (L < R) {
int mid = (L + R) / 2;
vector<int> tmp = cur;
// 對未確定的 switch，在 [L, mid] 範圍 flip
for (int j = L; j <= mid; j++) {
if (!used[j]) tmp[j] ^= 1;
}
int res = tryCombination(tmp.data());
bool same;
if (base == -1) same = (res == -1);
else if (res == -1) same = false;
else same = (res > i) == (base > i);
if (!same) {
R = mid;
} else {
L = mid + 1;
}
}
int sw = L;
// 決定這個 switch 的正確狀態
vector<int> tmp = cur;
tmp[sw] = 1;
int res = tryCombination(tmp.data());
if (res == -1 || res > i) {
S[sw] = 1;
} else {
S[sw] = 0;
}
used[sw] = 1;
D[sw] = i;
}
answer(S.data(), D.data());
}
