#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
void exploreCave(int n) {
vector<int> S(n, -1); // S[door] = which switch opens it
vector<int> C(n, -1); // C[door] = which state opens it
vector<int> cur(n, 0); // current configuration (locked switches in correct state)
for (int i = 0; i < n; i++) {
// Build candidate list: switches not yet assigned
vector<int> cands;
for (int j = 0; j < n; j++)
if (S[i] == -1) { // switch j not yet used
// Check if j is already assigned as some door's switch
bool used = false;
for (int k = 0; k < i; k++) if (S[k] == j) { used = true; break; }
if (!used) cands.push_back(j);
}
// Determine id[i]: does state 0 or state 1 open door i?
// Try all candidates at state 0 (cur already has locked switches correct)
vector<int> probe(cur);
for (int j : cands) probe[j] = 0;
int ci; // correct state for door i's switch
if (tryCombination(probe.data()) <= i)
ci = 1; // state 0 doesn't open it, so state 1 does
else
ci = 0;
// Binary search for which candidate switch opens door i
int lo = 0, hi = (int)cands.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
vector<int> ask2(cur); // start from locked state
// Set left half [lo..mid] to correct state ci, rest to opposite
for (int j = lo; j <= mid; j++) ask2[cands[j]] = ci;
for (int j = mid+1; j <= hi; j++) ask2[cands[j]] = 1 - ci;
if (tryCombination(ask2.data()) > i)
hi = mid; // door i opened, switch is in left half
else
lo = mid + 1;
}
S[i] = cands[lo];
C[i] = ci;
cur[cands[lo]] = ci; // lock this switch permanently
}
// answer() takes: C[switch] = correct state, S[switch] = door it controls
// But we have S[door]->switch and C[door]->state, need to invert
vector<int> ansS(n), ansC(n);
for (int i = 0; i < n; i++) {
ansS[S[i]] = i; // switch S[i] controls door i -- actually re-check API
ansC[S[i]] = C[i];
}
answer(ansC.data(), ansS.data());
}
