#include "plants.h" #include<bits/stdc++.h> #define int long long #define pb push_back #define mp make_pair #define f0r(i,n) for(int i = 0; i<n; i++) #define FOR(i, k, n) for(int i = k; i<n; i++) #define vi vector<int> #define vvi vector<vi> #define pii pair<int,int> #define vb vector<bool> #define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl; #define dout(x) cout<<x<<' '<<#x<<'\n'; #define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<'\n'; using namespace std; int n,k; vi r; vector<set<int>>adj; vector<vi>rch; vi ans; void init(signed k, std::vector<signed> R) { n=R.size();::k=k; r.resize(n);f0r(i,n)r[i]=k-1-R[i]; ans.resize(n); f0r(i,n)ans[i]=-1; int timer = 0; int cnt = 0; vb vis(n); while(cnt < n){ // vout(r); int prev = -1; f0r(j,2*n){ int i = j % n; if(j>=n&&r[i]==0&&!vis[i]){ int d = ((i-prev)%n+n)%n; if(d >= k||d==0){ ans[i] = timer; int cur = i; cnt++; f0r(l,k-1){ cur--; if(cur==-1)cur=n-1; r[cur]--; } } } if(r[i]==0&&!vis[i])prev=i; } f0r(i,n)if(ans[i]==timer)vis[i]=1; timer++; } /* graph idea failed adj.resize(n); rch.resize(n); f0r(i,n)rch[i].resize(n); f0r(i, n){ int p = i; int d = 0; f0r(j,k-1){ p++; p%=n; d++; if(r[i]>=r[p]+d)adj[i].insert(p); if(r[p]>=r[i]+d)adj[p].insert(i); if(r[i]==0)adj[p].insert(i); if(r[i]==k-1)adj[i].insert(p); } } f0r(i,n){ queue<int>q; vb vis(n); vis[i]=1,q.push(i); while(!q.empty()){ int node = q.front(); q.pop(); for(auto u : adj[node])if(!vis[u]){ vis[u]=1,q.push(u); } } f0r(j,n)rch[i][j]=vis[j]; } */ } signed compare_plants(signed x, signed y) { /* graph if(rch[x][y]==rch[y][x])return 0; if(rch[x][y])return 1; return -1; */ if(ans[x]==ans[y])return 0; if(ans[x]<ans[y])return -1; return 1; }