#include "cave.h" #include<bits/stdc++.h> void exploreCave(int n) { int a[n]; memset(a,0,sizeof a); int d[n]; for(int i=0; i<n; i++) d[i] = i; int done[n]; memset(done,0,sizeof done); int x; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(!done[j]) { a[j] = 0; } } x = tryCombination(a); if(x<0 || x>i) { for(int j=0; j<n; j++) { if(!done[j]) a[j] = 1; } } int l = 0; int r = n-1; int ans = n-1; while(l<=r) { int mid = l + (r-l)/2; for(int j=l; j<=mid; j++) { if(!done[j]) { a[j]^=1; } } x = tryCombination(a); if(x<0 || x>i) { for(int j=l; j<=mid; j++) { if(!done[j]) a[j]^=1; } ans = mid; r = mid-1; } else l = mid + 1; } done[ans] = 1; d[ans] = i; a[ans]^=1; } // int i=tryCombination(a); // while(i!=-1) // { // a[d[i]] ^=1; // i = tryCombination(a); // } answer(a,d); }