#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
/*void answer(vector<int> i, vector<int> j)
{
cout << "ANSWER with key Indexes = " << endl;
for (int item : i)
{
cout << item << " ";
}
cout << endl << "key States = " << endl;
for (int item : j)
{
cout << item << " ";
}
cout << endl;
}
//TESTING
int tryCombination(vector<int> q)
{
for (int item : q)
{
cout << item << " ";
}
cout << endl;
int a;
cin >> a;
return a;
}*/
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;
if (tryCombination(ans)>k)
{
// 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);
}
}
int a = tryCombination(q);
if (a > k)
{
// 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);
}*/
