Submission #1222192

#TimeUsernameProblemLanguageResultExecution timeMemory
1222192kargneqComparing Plants (IOI20_plants)C++20
0 / 100
0 ms328 KiB
#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; } } } if (idx == -1) 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 (len == 0) return 0; // x and y are the same 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...