#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); bool f = 0; if(p == i)f = 1; 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(f){ if(p != i)r = m; else l = m + 1; }else{ if(p == i)r = m; else l = m + 1; } } D[l] = i; if(f)S[l] = 1 - S[l]; valid[l] = 1; } answer(S,D); // return; }