#Question http://www.ioinformatics.org/locations/ioi13/contest/day2/cave/cave.pdf

#Code

#include "cave.h"
#include <cstdio>
#include <cstring>
using namespace std;
 
const int MAXN = 5001;
int status[MAXN] , door[MAXN] , guess[MAXN];
 
void exploreCave(int N){
  memset(door , -1 , sizeof(door));
  for(int n = 0 ; n < N ; n++){
    int r = tryCombination(status);
    int low = 0 , high = N - 1;
    while(low != high){
      bool changed = false;
      int a = low , b = (low + high) / 2;
      for(int i = 0 ; i < N ; i++){
        if(i >= a && i <= b){
          if(door[i] != -1){
            guess[i] = status[i];
          }
          else {
            guess[i] = !status[i];
            changed = true;
          }
        }
        else guess[i] = status[i];
      }
      int K = r;
      if(changed) K = tryCombination(guess);
      if(r == n){
        if(K > n || K == -1)
          high = b;
        else low = b + 1;
      }
      else {
        if(K == n) high = b;
        else low = b + 1;
      }
    }
    door[low] = n;
    if(r == n) status[low] = !status[low];
  }
    answer(status , door);
}

#Issue While this is a working and correct code, I runs at O(NlogN) time(I think). Is there a possible way to further shorten the time complexity? This code uses binary search.