Submission #1222186

#TimeUsernameProblemLanguageResultExecution timeMemory
1222186kargneqComparing Plants (IOI20_plants)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; vector<int> r; vector<int> prefix; vector<int> height; int n, k; bool built = false; // Subtask 1: k == 2 void build_prefix() { prefix.assign(n + 1, 0); for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + r[i]; } // Subtasks 2 & 3: 2k > n 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)) { // Check if all previous k-2 are used 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]--; } } built = true; } void init(int kk, std::vector<int> rr) { r = rr; n = r.size(); k = kk; built = false; 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; if (l < r_) { if (prefix[r_] - prefix[l] == 0) return 1; if (prefix[r_] - prefix[l] == r_ - l) return -1; } else { int sum = (prefix[n] - prefix[l]) + prefix[r_]; if (sum == 0) return 1; if (sum == (n - l) + r_) return -1; } return 0; } else if (2 * k > n) { // Subtasks 2 & 3: Build a possible configuration and compare heights if (!built) build_heights(); if (height[x] > height[y]) return 1; if (height[x] < height[y]) return -1; return 0; } // For other cases, not implemented 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...