#include <bits/stdc++.h>
using namespace std;
vector<int> r;
vector<int> prefix;
vector<int> height;
int n, k;
void build_prefix() {
prefix.assign(n + 1, 0);
for (int i = 0; i < n; ++i)
prefix[i + 1] = prefix[i] + r[i];
}
void build_heights() {
height.assign(n, 0);
vector<int> rr = r;
set<int> used;
for (int h = n; h >= 1; --h) {
int idx = -1;
for (int i = 0; i < n; ++i) {
if (rr[i] == 0 && !used.count(i)) {
bool ok = true;
for (int j = 1; j < k; ++j) {
int prev = (i - j + n) % n;
if (!used.count(prev) && rr[prev] == 0) {
ok = false;
break;
}
}
if (ok) {
idx = i;
break;
}
}
}
height[idx] = h;
used.insert(idx);
for (int j = 1; j < k; ++j) {
int prev = (idx - j + n) % n;
if (!used.count(prev))
rr[prev]--;
}
}
}
void init(int kk, std::vector<int> rr) {
r = rr;
n = r.size();
k = kk;
if (k == 2) build_prefix();
else if (2 * k > n) build_heights();
}
int compare_plants(int x, int y) {
if (k == 2) {
// Subtask 1: Use prefix sums
int l = (x + 1) % n, r_ = y;
int sum = 0, len = 0;
if (l <= r_) {
sum = prefix[r_] - prefix[l];
len = r_ - l;
} else {
sum = (prefix[n] - prefix[l]) + prefix[r_];
len = (n - l) + r_;
}
if (sum == 0) return 1;
if (sum == len) return -1;
return 0;
} else if (2 * k > n) {
// Subtasks 2 & 3: Compare reconstructed heights
if (height[x] > height[y]) return 1;
if (height[x] < height[y]) return -1;
return 0;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |