#include "cave.h" #include <bits/stdc++.h> using namespace std; int s[6000]; int d[6000]; int used[6000]; int last; bool First; bool check(int l, int r){ for(; l <= r;l++){ if(used[l] == 1)continue; s[l] = 1; } int temp1 = tryCombination(s); for(; l <= r;l++){ if(used[l] == 1)continue; s[l] = 0; } int temp2 = tryCombination(s); if(temp1 >= last){ First = 1; return temp2 >= last; }else { First = 0; return temp1 >= last; } } void exploreCave(int n) { for(int door = 0; door < n; door ++ ){ last = door+1; int l=0, r=n; while(l+1 < r){ int mid = (l+r)/2; if(check(l, mid)){ r = mid; }else { l = mid; } } d[door] = l; s[door] = First; used[door] = 1; } answer(s, d); } /* 4 1 1 1 0 3 1 0 2 */