#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
int s[5069], d[5069], unk[5069], lo, hi, mi;
int conv(int x)
{
if (x == -1) return 5001;
return x;
}
void exploreCave(int n)
{
int i, j, m;
//mulai dari 000000
//d[i] --> switch i door apa
//unk --> array yang buat switch apa aja yang belum tahu connect ke door apa (unknown)
for (i=0; i<=n-1; i++) s[i] = 0;
for (i=0; i<=n-1; i++) d[i] = -1;
//tentuin tiap door dari 0, 1, ... n-1 switchnya apa
for (i=0; i<=n-1; i++)
{
for (j=0, m=-1; j<=n-1; j++)
{
if (d[j] == -1) unk[++m] = j;
}
if (tryCombination(s) != i)
{
//flip semua switch unkwon, karena switch unknown connect ke door yang indeksnya >=i
for (j=0; j<=m; j++) s[unk[j]] ^= 1;
}
//pasti switch yang connect ke door i ketutup boz (tryCombination(s) == i)
//tinggal daffanandabinser mainin switch yang unknown, switch mana nich yang connect ke door i
for (lo=0, hi=m; lo<=hi; )
{
mi = (lo+hi)/2;
for (j=0; j<=mi; j++) s[unk[j]] ^= 1;
if (conv(tryCombination(s))>i) hi = mi-1; //yang paling kiri dan door i kebuka adalah switchnya :D
else lo = mi+1;
for (j=0; j<=mi; j++) s[unk[j]] ^= 1;
}
s[unk[hi+1]] ^= 1;
d[unk[hi+1]] = i;
}
answer(s, d);
}
