#include "cave.h"
#include <vector>
#include <iostream>
using namespace std;
#define D(a) \
do { cout << #a " " << (a) << " ";} while(false)
const int mxN = 5010;
int myn, blockingdoor,zeroes,dif,foundcnt;
int door[mxN],combi[mxN];
vector<int> range;
void makeRange() {
// maakt een vector met alle deuren die nog niet zijn gevonden
range.clear();
//cout << "range: ";
for(int i=0;i<myn;++i) {
if(door[i]==-1) {
range.push_back(i);
//cout << i;
}
} //cout << endl;
}
int getTry(int l, int r) {
for(int i=l;i<=r;++i) {
combi[range[i]] = 1;
}
//cout << "trying ";
// for(int i=0;i<myn;++i) {
// cout << combi[i];
// } cout << ' ';
int ans = tryCombination(combi);
for(int i=l;i<=r;++i) {
combi[range[i]] = 0;
}
if(ans==-1) ans = 1e9-1;
return ans;
}
bool explore(int l,int r, bool dotry=true, int prevans=-1) {
//D(l);D(r);cout <<endl;
int mytry, mid = (l+r)/2;
if(dotry) {
mytry = getTry(l,r);
//D(mytry);cout << endl;
}
else mytry = prevans;
if(l==r) {
// aangekomen bij een enkel element in de binary search
if(mytry>zeroes) { // Blockingdoor is kennelijk opengegaan
door[range[l]] = zeroes;
blockingdoor = range[l];
//cout << "found blockingdoor\n";
foundcnt++;
return true;
} else if(mytry<zeroes) { // Een andere deur blokkeert nu
door[range[l]] = mytry;
foundcnt++;
return true;
}
else return false;
}
if(mytry>zeroes or mytry<zeroes) {
bool found = explore(l,mid,true,mytry);
if(foundcnt>=dif) { // alle deuren voor de blockingdoor en de blockingdoor zelf zijn gevonden
//cout << "No more\n";
return true;
}
explore(mid+1,r,found,mytry);
return true;
}
// mytry blokkeert nog steeds de blockingdoor en blokkeert geen enkele deur ervoor. geen extra info
return false;
}
using namespace std;
void exploreCave(int N) {
blockingdoor=-1;zeroes=-1;myn = N;
for(int i=0;i<myn;++i) {door[i]=-1;combi[i]=0;}
while(true) {
makeRange();
if(range.size()==0) break;
int prevzeroes=zeroes;
zeroes = getTry(0,-1);
dif = zeroes-prevzeroes;
foundcnt = 0;
//D(zeroes);cout << endl;
explore(0,range.size()-1);
// de blockingdoor is gevonden, deze stond op nul, nu zetten we hem op 1
if(blockingdoor!=-1) combi[blockingdoor] = 1;
}
answer(combi,door);
}
