#include <bits/stdc++.h>
#include "cave.h"
#define MAX_N 5000
using namespace std;
int tryCombination(int S[]);
void answer(int S[], int D[]);
int id[MAX_N + 1];
int v[MAX_N + 1];
const int UNDEF = -1;
int q[MAX_N + 1];
void baga(int st, int dr, int val)
{
for(int i = st; i <= dr; i ++)
{
//cout << " BAGAM " << i << " " << val << "\n";
//cout << " AVEM " << v[i] << " == " << UNDEF << " " << (v[i] == UNDEF) << "\n";
q[i] = (v[i] == UNDEF ? val : v[i]);
}
}
int tmp[MAX_N + 1];
int n;
void copyV(int a[], int b[])
{
for(int i = 0; i < n; i ++)
a[i] = b[i];
}
void doSpec()
{
for(int i = 0; i < n; i ++)
{
if(v[i] == UNDEF)
{
q[i] = 1 - q[i];
int x = tryCombination(q);
id[i] = x;
v[i] = 1 - q[i];
q[i] = 1 - q[i];
}
}
answer(v, id);
}
int done[MAX_N + 1];
int CATE = 0;
int ap[MAX_N + 1];
int APEL;
void divide(int st, int dr, int idx, int val)
{
// cout << " INTRA " << st << " " << dr << " " << idx << " " << val << "\n";
if(st == dr)
{
// cout << " PE POZ " << st << " ARE VAL " << val << " SI ID " << idx << "\n";
id[st] = idx;
v[st] = val;
q[st] = val;
done[idx] = 1;
CATE ++;
return;
}
/* cout << idx << " ESTE " << done[idx] << "\n";
for(int i = 0; i < n; i ++)
cout << v[i] << " ";
cout << "\n";
for(int i =0 ; i < n; i++)
cout << id[i] << " ";
cout << "\n";*/
int tmp[MAX_N + 1];
int mid = (st + dr) >> 1;
while(done[idx] == 0)
{/*
cout << " SUNITEM " << st << " " << dr << " " << idx << " " << val << "\n";
for(int i =0; i <= 5; i ++)
cout << q[i ] << " " ;
cout << "\n";*/
copyV(tmp, q);
baga(st, mid, val);
/*
for(int i =0; i <= 5; i ++)
cout << q[i ] << " " ;
cout << "\n";*//*
ap[idx] ++;
if(ap[idx] > 13)
cout << " +12 " << ap[idx] << " " << idx << "\n";*/
int x = tryCombination(q);
APEL ++;
/* ap[x] ++;
if(ap[x] > 10)
cout << "" << x << " PESTE 10 " << ap[x] << "\n";*/
// cout << "PR ++ " << x << "\n";
/* for(int i =0 ; i < n; i++)
cout << q[i] << " ";
cout << "\n";*/
if(x == -1)
doSpec();
if(x < idx)
{
divide(st, mid, x, 1 - val);
copyV(q, tmp);
}
else
if(x == idx)
{
divide(mid + 1, dr, idx, val);
copyV(q, tmp);
}
else
if(x > idx)
{
copyV(q, tmp);
divide(st, mid, idx, val);
}
}
}
void bagaRand()
{
for(int i = 0; i < n; i ++)
{
q[i] = (v[i] == UNDEF ? rand() % 2 : v[i]);
}
}
void exploreCave(int N)
{
srand(time(0));
n = N;
for(int i = 0; i < N; i ++)
{
v[i] = UNDEF;
id[i] = UNDEF;
q[i] = 0;
}
while(CATE < N)
{
baga(0, N, 0);
int x = tryCombination(q);
APEL ++;
/* ap[x] ++;
if(ap[x] > 10)
cout << "" << x << " PESTE 10 " << ap[x] << "\n";*/
// cout << " PRIMA E " << x << " " << APEL << " " << APEL / 14 << "\n";
if(x == -1)
doSpec();
divide(0, N, x, 1);
// bagaRand();
}
answer(v, id);
}
