#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
int is_fixed[5005], gen_fixed[5005];
bool check(int n, int door, int index)
{
int c[n];
for (int i = 0 ; i < n ; ++ i)
c[i] = 0;
int cnt = 0;
for (int i = 0; i < n; ++ i )
{
if(is_fixed[i])c[i] = gen_fixed[i];
else
{
cnt ++;
if(cnt <= index)c[i] = 0;
else c[i] = 1;
}
}
int feedback = tryCombination(c);
return (feedback > door || feedback == -1);
}
bool check2(int n, int door, int index)
{
int c[n];
int cnt = 0;
for (int i = 0; i < n; ++i)
c[i] = 0;
for (int i = 0; i < n; ++ i )
{
if(is_fixed[i])c[i] = gen_fixed[i];
else
{
cnt ++;
if(cnt <= index)c[i] = 1;
else c[i] = 0;
}
}
int feedback = tryCombination(c);
//cout << "na " << index << " " << feedback << endl;
return (feedback > door || feedback == -1);
}
void exploreCave(int N)
{
int n = N;
int s[n], feedback;
int fixed[n]; /// opravi i gen_fixed
int d[n];
for (int i = 0; i < n; ++ i)
{
fixed[i] = 0;
s[i] = 0;
d[i] = 0;
}
for (int i = 0; i < n; ++ i)
{
feedback = tryCombination(s);
if(feedback == -1 || feedback > i) /// s 0 se otvarq, vsichko 1ici pyrvata mid-nata 0 kydeto se otvarq
{
/// edinici
int l = 1, r = n-i, mid, ans = 1;
while(l <= r)
{
mid = (l + r)/2;
if(check(n, i, mid))
{
r = mid - 1;
ans = mid;
}
else l = mid + 1;
}
int cnt_non = 0;
for (int j = 0; j < n; ++ j)
{
if(is_fixed[j])continue;
cnt_non ++;
if(cnt_non == ans)
{
fixed[j] = 0;
gen_fixed[j] = 0;
is_fixed[j] = 1;
d[j] = i;
s[j] = 0;
//cout << i << " " << j << " " << fixed[j] << endl;
break;
}
}
}
else /// s 1 se otvarq, pyrvoto promeneno na 1ci kydeot stava
{
int l = 1, r = n-i, mid, ans = 1;
while(l <= r)
{
mid = (l + r)/2;
if(check2(n, i, mid))
{
r = mid - 1;
ans = mid;
}
else l = mid + 1;
}
int cnt_non = 0;
for (int j = 0; j < n; ++ j)
{
if(is_fixed[j])continue;
cnt_non ++;
if(cnt_non == ans)
{
fixed[j] = 1;
gen_fixed[j] = 1;
is_fixed[j] = 1;
d[j] = i;
s[j] = 1;
//cout << i << " " << j << " " << fixed[j] << endl;
break;
}
}
}
}
answer(fixed, d);
}
