#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
const int maxN = 5007;
const int MAX_CALLS = 70000;
int n, s[maxN], d[maxN], vis[maxN];
//int realS[maxN], realD[maxN], inv[maxN];
//int num_calls;
//
//void answer(int S[], int D[]) {
// int i;
// bool correct = 1;
// for (i = 0; i < n; ++i)
// if (S[i] != realS[i] || D[i] != realD[i]) {
// correct = 0;
// break;
// }
// if (correct) cout << "CORRECT\n";
// else {
// cout << "INCORRECT\n";
// for(int i = 0; i < n; ++i) {
// cout << realS[i] << ' ';
// }
// cout << '\n';
// for(int i = 0; i < n; ++i) {
// cout << realD[i] << ' ';
// }
// }
// exit(0);
//}
//
//int tryCombination(int S[]) {
// int i;
//
// if (num_calls >= MAX_CALLS) {
// cout << "INCORRECT\nToo many calls to tryCombination().\n"; exit(0);
// }
// ++num_calls;
// for (i = 0; i < n; ++i)
// if (S[inv[i]] != realS[inv[i]])
// return i;
// return -1;
//}
//
//int init()
//{
// srand(time(0));
// int n = rand() % 10;
// for(int i = 0; i < n; ++i) realS[i] = rand() % 2, realD[i] = i;
// random_shuffle(realD, realD + n);
// for(int i = 0; i < n; ++i) inv[realD[i]] = i;
// return n;
//}
bool Chk(int mid, int pos)
{
for(int i = 0; i < n; ++i) {
if(!vis[i]) {
if(mid) --mid, s[i] = 1;
else s[i] = 0;
}
}
int door = tryCombination(s);
return door == -1 || door > pos;
}
void exploreCave(int sz)
{
n = sz;
fill_n(s, n + 1, 0);
fill_n(vis, n + 1, 0);
for(int i = 0; i < n; ++i) {
int cur = tryCombination(s);
bool open = 0;
if(cur == -1 || cur > i) open = 1;
int low = 0, high = n - i;
while(low <= high) {
int mid = (low + high) / 2;
if(Chk(mid, i) != open) high = mid - 1;
else low = mid + 1;
}
for(int j = 0; j < n; ++j) {
if(!vis[j]) --low, s[j] = 0;
if(!low) {
open? s[j] = 0: s[j] = 1;
d[j] = i, vis[j] = 1; break;
}
}
}
answer(s, d);
}
//
//int main() {
// int n;
// n = init();
// exploreCave(n);
// printf("INCORRECT\nYour solution did not call answer().\n");
// return 0;
//}
