#include "cave.h" #include <bits/stdc++.h> using namespace std; void exploreCave(int N) { vector<int> S(N, 0), D(N, -1); vector<int> fixedState(N, -1); vector<int> rem; rem.reserve(N); for (int i = 0; i < N; i++) rem.push_back(i); for (int door = 0; door < N; door++) { for (int i = 0; i < N; i++) { if (fixedState[i] != -1) S[i] = fixedState[i]; else S[i] = 0; } int r = tryCombination(S.data()); int need = (r == door ? 1 : 0); int lo = 0, hi = (int)rem.size() - 1; while (lo < hi) { int mid = (lo + hi) >> 1; for (int i = 0; i < N; i++) { if (fixedState[i] != -1) S[i] = fixedState[i]; else S[i] = (need ^ 1); } for (int k = lo; k <= mid; k++) S[rem[k]] = need; int x = tryCombination(S.data()); bool ok = (x == -1 || x > door); if (ok) hi = mid; else lo = mid + 1; } int sw = rem[lo]; fixedState[sw] = need; D[sw] = door; rem.erase(rem.begin() + lo); } for (int i = 0; i < N; i++) S[i] = fixedState[i]; answer(S.data(), D.data()); }