#include <bits/stdc++.h> #include "plants.h" using namespace std; int n; vector <vector<int>> v; vector <bitset<200005>> b; void init(int k, std::vector<int> r) { n = r.size(); v.assign(n, {}); b.assign(n, bitset<200005>()); for (int i = 0; i < n; i++) { if (r[i] == 0) { for (int j = i+1; j <= i+k-1; j++) { int id = j%n; v[i].emplace_back(id); } } else if (r[i] == k-1) { for (int j = i+1; j <= i+k-1; j++) { int id = j%n; v[id].emplace_back(i); } } } auto toposort = [](int n, vector <vector<int>>& v) { vector <int> indeg(n+5,0); for (int i = 0; i < n; i++) { for (auto to:v[i]) { indeg[to]++; } } queue <int> q; for (int i = 0; i < n; i++) { if (indeg[i] == 0) { q.push(i); } } vector <int> res; while (!q.empty()) { int f = q.front(); q.pop(); res.emplace_back(f); for (auto to:v[f]) { if (--indeg[to] == 0) { q.push(to); } } } reverse(res.begin(),res.end()); return res; }; vector <int> res = toposort(n,v); for (int i1 = 0; i1 < res.size(); i1++) { int i = res[i1]; b[i].set(i); for (auto to:v[i]) { b[i] |= b[to]; } } } int compare_plants(int x, int y) { if (b[x][y] == 1) { return 1; } if (b[y][x] == 1) { return -1; } return 0; }