#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
/*void answer(int i[5002], int j[5002])
{
int N = 4;
cout << "ANSWER with key Indexes = " << endl;
for (int c = 0; c < N; c++)
{
cout << i[c] << " ";
}
cout << endl << "key States = " << endl;
for (int c= 0 ; c < N; c++)
{
cout << j[c] << " ";
}
cout << endl;
}
//TESTING
int tryCombination(int q[5002])
{
vector<int> k_i = {1,0,1,0};
vector<int> k_p = {2,3,0,1};
int min = 6700; // 6 7 !
int N = 4;
for (int c= 0; c < N; c++)
{
cout << q[c] << " ";
if (q[c]!=k_i[c]&&k_p[c]<min)
{
min = k_p[c];
}
}
cout << "|";
if (min==6700)
{
cout << "ANS = -1" << endl;
return -1;
}
else{
cout << "ANS = " << min << endl;
return min;
}
}*/
void binarySearch(int k, int n, int keyIndex[5002], int keyState[5002])
{
// logN binary search to find key
int ans[5002];
for (int i = 0; i < n; i++)
{
if (keyState[i] == -1)
{
ans[i]=0;
}
else{
ans[i] = keyState[i];
}
}
int pos = 1;
int a = tryCombination(ans);
if (a>k || a==-1)
{
// correct position for switch is down
pos = 0;
}
// binary search
int start = 0;
int end = n;
while ((end-start)>1)
{
int mid = (start+end)/2;
int q[5002];
for (int i = 0; i < n; i++)
{
if (keyState[i]!=-1)
{
q[i]=keyState[i];
}
// first we query range(start..mid)
else if (i >= start && i < mid)
{
// we want to query this i
q[i] = pos;
}
else{
// not in query --> use off position.
q[i] = abs(pos-1);
}
}
a = tryCombination(q);
if (a > k || a==-1)
{
// first closed door after k so k must be open.
end = mid;
}
else{
start = mid;
}
}
// binary search is over so start==end (covers 1)
keyIndex[start] = k;
keyState[start] = pos;
}
void exploreCave(int N)
{
int keyIndex[5002];
fill_n(keyIndex,5002,-1);
int keyState[5002];
fill_n(keyState,5002,-1);
for (int i = 0; i < N; i++)
{
binarySearch(i,N,keyIndex,keyState);
}
answer(keyState,keyIndex);
}
/*// TESTING
int main()
{
int N;
cin >> N;
exploreCave(N);
}*/
