#include <stdio.h> #include <stdlib.h> #include <vector> #include <iostream> #include "cave.h" using namespace std; void exploreCave(int n) { int a[n],s[n]; vector<int>c; for(int i=0;i<n;i++){ c.push_back(i); a[i] = 0; } for(int i=0;i<n;i++){ int res = tryCombination(a); int m = c.size(); if(res!= -1 && res <= i){ int l = 0,r = m-1; while(r>l){ int mid = (l+r)/2; for(int j=0;j<=mid;j++)a[c[j]]^=1; int cc = tryCombination(a); if(cc==-1 || cc>i)r = mid; else l = mid+1; for(int j=0;j<=mid;j++)a[c[j]]^=1; } s[i] = c[r]; a[c[r]]^=1; c.erase(c.begin() + r); }else{ int l = 0,r = m-1; while(r>l){ int mid = (l+r)/2; for(int j=0;j<=mid;j++)a[c[j]]^=1; int cc = tryCombination(a); if(cc!=-1 && cc<=i)r = mid; else l = mid+1; for(int j=0;j<=mid;j++)a[c[j]]^=1; } s[i] = c[r]; c.erase(c.begin() + r); } } int b[n]; for(int i=0;i<n;i++)b[s[i]] = i; answer(a,b); }