#include <bits/stdc++.h> #include "cave.h" using namespace std; void exploreCave(int N) { int S[N], D[N]; bool vis[N + 1]; for(int i = 0; i < N; ++i) S[i] = 0, D[i] = i, vis[i] = 0; auto ok = [&](int x, int r) -> bool { int NS [N]; for(int i = 0; i < N; ++i) NS[i] = S[i]; for(int i = 0; i <= r; ++i){ if(!vis[i]) NS[i] ^= 1; } return tryCombination(NS) ^ x; }; for(int i = 0; i < N; ++i){ int pos = tryCombination(S); bool locked = 0; if(pos == i) locked = 1; int st = 0, en = N - 1, org = 0; while(st <= en){ int mid = st + (en - st) / 2; if(ok(i, mid)) org = mid, en = mid - 1; else st = mid + 1; } S[org] ^= locked, vis[org] = 1, D[org] = i; } answer(S, D); }