#include "cave.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
const int MAXN = 5000;
int n;
int answered[MAXN];
int bind[MAXN];
int lever[MAXN];
int tryCombination(int S[]);
void answer(int S[], int D[]);
void flip(int arr[], int idx)
{
for(int i = 0 ; i <= idx ; ++i)
{
if(answered[i])
{
continue;
}
arr[i] ^= 1;
}
}
bool f(int doorIdx, bool wasClosed, int leverIdx)
{
flip(lever, leverIdx);
int res = tryCombination(lever);
flip(lever, leverIdx);
if(wasClosed)
{
return res != doorIdx;
}
else
{
return res == doorIdx;
}
}
void exploreCave(int N)
{
n = N;
std::fill(answered, answered + n, 0);
std::fill(lever, lever + n, 0);
for(int i = 0 ; i < n ; ++i)
{
bool isClosed = (tryCombination(lever) == i);
int l = -1, r = n - 1;
while(l + 1 < r)
{
int mid = (l + r) / 2;
if(!f(i, isClosed, mid)) l = mid;
else r = mid;
}
//std::cout << i << " " << r << "\n";
answered[r] = 1;
bind[r] = i;
if(isClosed)
{
lever[r] ^= 1;
}
}
answer(lever, bind);
}
