#include "plants.h"
#include <iostream>
#include <algorithm>
#include <queue>
#define ll long long
#define maxn 200005
using namespace std;
vector<int> v, one, zero, ind1, ind0, arr;
int k;
int n;
int seg[4 * maxn], tag[4 * maxn];
vector<int> ze;
void ini(int cur, int l, int r) {
if (r <= l) return;
if (r - l == 1) {
seg[cur] = v[l];
return;
}
int mid = (l + r) / 2;
ini(cur * 2, l, mid);
ini(cur * 2 + 1, mid, r);
seg[cur] = min(seg[cur * 2], seg[cur * 2 + 1]);
}
void modify(int cur, int l, int r, int ql, int qr) {
if (r <= l || ql >= r || qr <= l) return;
if (ql <= l && qr >= r) {
tag[cur]++;
return;
}
int mid = (l + r) / 2;
modify(cur * 2, l, mid, ql, qr);
modify(cur * 2 + 1, mid, r, ql, qr);
seg[cur] = min(seg[cur * 2] - tag[cur * 2], seg[cur * 2 + 1] - tag[cur * 2 + 1]);
}
void sz(int cur, int l, int r, int x) {
if (r <= l) return;
//cout << l << " " << r << " " << seg[cur] - tag[cur] - x << endl;
if (r - l == 1) {
if (seg[cur] - tag[cur] - x == 0) {
ze.push_back(l);
tag[cur] = -1000000;
}
return;
}
int mid = (l + r) / 2;
if (seg[cur * 2] - tag[cur * 2] - x - tag[cur] == 0) {
sz(cur * 2, l, mid, x + tag[cur]);
}
if (seg[cur * 2 + 1] - tag[cur * 2 + 1] - x - tag[cur] == 0) {
sz(cur * 2 + 1, mid, r, x + tag[cur]);
}
seg[cur] = min(seg[cur * 2] - tag[cur * 2], seg[cur * 2 + 1] - tag[cur * 2 + 1]);
}
bool cmp(int a, int b) {
if (a < b) {
return a + k < b;
} else {
return (a + k) < b + n;
}
}
void init(int K, vector<int> r) {
v = r;
n = r.size();
arr.resize(n);
k = K;
if (K == 2) {
int cnt = 0, cur = 0;
one.push_back(cnt);
for (int i = 0;i < n;i++) {
if (r[i] == 0) {
ind1.push_back(cur);
cur = i + 1;
cnt++;
}
one.push_back(cnt);
}
if (r[n - 1] == 1) {
for (int i = n - 1;i >= 0;i--) {
if (one[i] == cnt) ind1[0] = i;
one[i] %= cnt;
}
}
cnt = 0, cur = 0;
zero.push_back(cnt);
for (int i = 0;i < n;i++) {
if (r[i] == 1) {
ind0.push_back(cur);
cur = i + 1;
cnt++;
}
zero.push_back(cnt);
}
if (r[n - 1] == 0) {
for (int i = n - 1;i >= 0;i--) {
if (zero[i] == cnt) ind0[0] = i;
zero[i] %= cnt;
}
}
} else {
ini(1, 0, n);
priority_queue<int, vector<int>, bool(*) (int, int) > pq(cmp);
for (int i = n;i >= 1;i--) {
sz(1, 0, n, 0);
//cout << endl;
for (int j:ze) {
//cout << j << ' ';
pq.push(j);
}
//cout << endl;
ze.clear();
int ind = pq.top();
pq.pop();
arr[ind] = i;
if (ind - k + 1 < 0) {
modify(1, 0, n, 0, ind + 1);
modify(1, 0, n, n - k + ind + 1, n);
} else {
modify(1, 0, n, ind - k + 1, ind + 1);
}
}
//for (int i = 0;i < n;i++) cout << arr[i] << " ";
//cout << endl;
}
return;
}
int compare_plants(int x, int y) {
if (k == 2) {
if (one[x] != one[y] && zero[x] != zero[y]) {
return 0;
} else {
if (one[x] == one[y]) {
//cout <<(x - ind1[one[x]] + n) % n << " " << (y - ind1[one[y]] + n) % n << endl;
if ((x - ind1[one[x]] + n) % n < (y - ind1[one[y]] + n) % n) return -1;
else return 1;
} else {
if ((x - ind0[zero[x]] + n) % n < (y - ind0[zero[y]] + n) % n) return 1;
else return -1;
}
}
} else {
return arr[x] > arr[y] ? 1 : -1;
}
}
/*
5 1 3
1 1 0 0 1
0 1
0 3
2 4
7 4 5
3 1 2 2 0 1 2
0 3
2 4
3 6
1 5
2 5
*/
