#include "cave.h" #include <bits/stdc++.h> using namespace std; vector<int> filp(int S[],bool valid[],int N,int l,int r){ vector<int> comb(N); for(int i = 0;i < N;i++){ if(l <= i && i <= r){ if(!valid[i])comb[i] = 1 - S[i]; else comb[i] = S[i]; }else comb[i] = S[i]; } return comb; } void exploreCave(int N) { int S[N],D[N]; for(int i = 0;i < N;i++)S[i] = 0; for(int i = 0;i < N;i++)D[i] = 0; bool valid[N]; for(int i = 0;i < N;i++)valid[i] = 0; for(int i = 0;i < N;i++){ int p = tryCombination(S); int l = 0,r = N - 1,ans = -1; while(l <= r){ int m = (l + r)/2; vector<int> comb = filp(S,valid,N,l,m); int Ncomb[N]; for(int j = 0;j < N;j++)Ncomb[j] = comb[j]; int s = tryCombination(Ncomb); if(p == s)l = m + 1; else{ ans = m; r = m - 1; } } D[ans] = i; if(p == i)S[ans] = 1 - S[ans]; valid[ans] = 1; } answer(S,D); // return; }