#include "plants.h"
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
namespace {
using i64 = long long;
using namespace std;
template <class T>
using vec = vector<T>;
template <class T>
istream& operator>>(istream& is, vec<T>& X) {
for (auto& x : X) {
is >> x;
}
return is;
}
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;
bool posse = false;
int N;
vec<int> id_lt, id_gt;
struct Unionfind {
vec<int> p;
Unionfind(int N) : p(N, -1) {};
int find(int x) {
return p[x] < 0 ? x : (p[x] = find(p[x]));
}
void join(int x, int y) {
if ((x = find(x)) == (y = find(y))) {
return;
}
p[x] += exchange(p[y], x);
}
bool same(int x, int y) {
return find(x) == find(y);
}
};
}
void init(int k, std::vector<int> r) {
if (k == 2) {
posse = true;
}
N = size(r);
id_lt.resize(N), id_gt.resize(N);
Unionfind uf(N);
for (int i = 0; i < N; i++) {
int j = (i + 1) % N;
if (r[i] == 1) {
uf.join(i, j);
}
}
for (int i = 0; i < N; i++) {
id_lt[i] = uf.find(i);
}
fill(ALL(uf.p), -1);
for (int i = 0; i < N; i++) {
int j = (i + 1) % N;
if (r[i] == 0) {
uf.join(i, j);
}
}
for (int i = 0; i < N; i++) {
id_gt[i] = uf.find(i);
}
}
int compare_plants(int x, int y) {
if (!posse) {
return 0;
}
auto get_posse = [](int l, int x) {
if (x < l) {
return N + x - l;
}
return x - l;
};
if (id_lt[x] == id_lt[y]) {
int l = id_lt[x];
return (get_posse(l, x) < get_posse(l, y) ? -1 : 1);
}
else if (id_gt[x] == id_gt[y]) {
int l = id_gt[x];
return (get_posse(l, x) < get_posse(l, y) ? 1 : -1);
}
else {
return 0;
}
}
