#include "plants.h"
#include <queue>
#include <bitset>
const int MN = 5e3+10;
const int INF = 0x3f3f3f3f;
int N, K, ts[MN], ctr;
bool v[MN];
std::vector<int> a[MN]; // i > a[i][...] -- dag
std::bitset<MN> vis[MN];
void dfs(int n)
{
v[n]=1;
for(int x:a[n])
if(!v[x])
dfs(x);
ts[ctr++]=n;
}
void init(int k, std::vector<int> r) {
K=k, N=r.size();
std::queue<int> q;
int zc=0;
for(int i=N-K;i<N;++i)
zc += !r[i];
for(int i=0;i<N;++i)
{
zc -= !r[(N-K+i)%N];
if(zc==0 && r[i]==0)
q.push(i);
zc += !r[i];
}
for(;!q.empty();)
{
int n=q.front(); q.pop();
if(r[n] < 0) continue;
// check
bool ok=1;
for(int i=1;i<K;++i)
if(r[(n-i+N)%N]==0)
ok=0;
if(!ok) continue;
// add
r[n]=-1;
for(int i=K-1;i>0;--i)
--r[(n-i+N)%N];
for(int i=1;i<K;++i)
if(r[(n+i)%N] >= 0)
{
a[n].push_back((n+i)%N);
if(r[(n+i)%N] == 0) q.push((n+i)%N);
//break;
}
for(int i=K-1;i>0;--i)
if(r[(n-i+N)%N] >= 0)
{
a[n].push_back((n-i+N)%N);
if(r[(n-i+N)%N] == 0) q.push((n-i+N)%N);
//break;
}
}
for(int i=0;i<N;++i)
if(!v[i])
dfs(i);
for(int i=0;i<N;++i)
vis[i].set(i);
for(int i=0;i<N;++i)
for(int x:a[ts[i]])
vis[ts[i]]|=vis[x];
return;
}
int compare_plants(int x, int y)
{
if(vis[x][y]) return 1;
if(vis[y][x]) return -1;
return 0;
}
