#include "cave.h" #include <bits/stdc++.h> using namespace std; void exploreCave(int N) { int S[N], D[N]; int comb[N]; vector<int> vec(N); iota(vec.begin(),vec.end(),0); for(int i = 0; i < N; i++){ for(auto u : vec) comb[u] = 0; for(int j = 0; j < i; j++) comb[D[j]] = S[D[j]]; int open = tryCombination(comb)==i; int l = -1, r = (int) vec.size()-1; while(l+1 < r){ int mid = (l+r)>>1; for(int j = 0; j < (int) vec.size(); j++) if(j <= mid) comb[vec[j]] = open^1; else comb[vec[j]] = open; for(int j = 0; j < i; j++) comb[D[j]] = S[D[j]]; if(tryCombination(comb)==i) r = mid; else l = mid; } D[i] = vec[r]; S[D[i]] = open; comb[D[i]] = open; vec.erase(vec.begin()+r); } answer(S,D); }