#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); // 是否已確定
auto ok = [&](int x, int i) {
// door i 是否是開的
return (x == -1 || x > i);
};
for (int i = 0; i < N; i++) {
vector<int> cur(N, 0);
// 已確定的固定，其餘先設 0
for (int j = 0; j < N; j++) {
if (used[j]) cur[j] = S[j];
else cur[j] = 0;
}
int base = tryCombination(cur.data());
// 在「未確定的 switch」中做二分
vector<int> cand;
for (int j = 0; j < N; j++) {
if (!used[j]) cand.push_back(j);
}
int L = 0, R = (int)cand.size() - 1;
while (L < R) {
int mid = (L + R) / 2;
vector<int> tmp = cur;
// flip cand[L..mid]
for (int k = L; k <= mid; k++) {
int j = cand[k];
tmp[j] ^= 1;
}
int res = tryCombination(tmp.data());
// 比較「door i 是否開」
if (ok(base, i) == ok(res, i)) {
// 沒影響 → 答案在右半
L = mid + 1;
} else {
// 有影響 → 在左半
R = mid;
}
}
int sw = cand[L];
// 決定這個 switch 的正確狀態
vector<int> tmp = cur;
tmp[sw] = 1;
int res = tryCombination(tmp.data());
if (ok(res, i)) {
S[sw] = 1;
} else {
S[sw] = 0;
}
used[sw] = 1;
D[sw] = i;
}
answer(S.data(), D.data());
}
