Submission #1211449

#TimeUsernameProblemLanguageResultExecution timeMemory
1211449fafnirComparing Plants (IOI20_plants)C++20
5 / 100
47 ms6600 KiB
#include <bits/stdc++.h> // #define LOCAL using namespace std; const int NMAX = 200'001; const int INF = NMAX+1; int n,k,q; int r[NMAX+1]; int h[NMAX+1]; // heights or INF if non-existing // Sum of r[l...r] = rpref[r+1] - rpref[l] int rpref[NMAX+1]; void init(int kl, vector<int> rl) { n = rl.size(); k = kl; for (int i = 0; i < n; ++i) { r[i] = rl[i]; h[i] = 1; } rpref[0] = 0; for (int i = 1; i <= n; ++i) { rpref[i] += rpref[i-1]; rpref[i] += r[i-1]; } if (2*k > n) { // Subtask 2 int curr = n-1; unordered_set<int> taken; for (int _ = 0; _ < n-1; ++_) { int prev = 0; for (int i = n-1; i >= n-1-(k-1)+1; --i) { prev += r[i] > 0; } int j = n-1-(k-1)+1; int pos = -1; for (int i = 0; i < n; ++i) { if (taken.count(i)) continue; if (r[i] == 0 && prev > 0) {pos = i; taken.insert(pos); break;} prev += r[i] > 0; prev -= r[j] > 0; j = (j+1) % n; } // assert (pos != -1); h[pos] = (n-_); int cnt = k-1; while (cnt >= 0) { int t = (pos-cnt); if (t < 0) t += n; r[t]--; cnt--; } } } } bool taller(int x, int y) { // Condition 1 // r[x...y-1] all 0 --> From x to y, all are smaller than x int c0 = rpref[y] - rpref[x]; if (c0 == 0) return true; // Condition 2 // r[y...n-1] & r[0...x-1] = 1 --> From y ... x, all are larger than y int c1 = 0; int l1 = 0; c1 += rpref[n] - rpref[y]; l1 += n-1-y+1; if (x > 0) { c1 += rpref[x] - rpref[0]; l1 += x-1-0+1; } if (l1 == c1) return true; return false; } bool smaller(int x, int y) { // Condition 1 // r[x...y-1] all 1 --> all larger than x int c0 = rpref[y] - rpref[x]; if (c0 == (y-1-x+1)) return true; int c1 = 0; c1 += rpref[n] - rpref[y]; if (x > 0) { c1 += rpref[x] - rpref[0]; } return c1 == 0; } // x, y: Labels of plants // Return: // 1: x taller than plant y // -1: x smaller than plant y // 0: inconclusive int compare_plants(int x, int y) { // Subtask 1 if (k == 2) { if (taller(x, y)) { return 1; } else if (smaller(x, y)) { return -1; } else { return 0; } } else if (2*k > n) { if (h[x] > h[y]) return 1; else if (h[x] < h[y]) return -1; return 0; } return -1; } #ifdef LOCAL int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); int nl, kl, ql; cin >> nl >> kl >> ql; vector<int> rl(nl); for (auto& e : rl) cin >> e; init(kl, rl); for (int _ = 0; _ < ql; _++) { int x, y; cin >> x >> y; cout << compare_plants(x, y); if (_ < ql-1) cout << '\n'; } return 0; } #endif
#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...