Submission #1211271

#TimeUsernameProblemLanguageResultExecution timeMemory
1211271fafnirComparing Plants (IOI20_plants)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> // #define LOCAL using namespace std; const int NMAX = 200'001; int n,k,q; int r[NMAX]; 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]; } rpref[0] = 0; for (int i = 1; i <= n; ++i) { rpref[i] += rpref[i-1]; rpref[i] += r[i-1]; } } bool isSmaller(int x, int y) { // Two conditions // i) r[x] = ... = r[y-1] = 1 int s0 = rpref[y] - rpref[x]; if (s0 == (y-1-x+1)) return true; // ii) r[y] = ... = r[n-1] = 1 and r[0] = ... = r[x-1] = 1 int s1 = rpref[n] - rpref[y+1]; s1 += rpref[x] - rpref[0]; if (s1 == 0) return true; return false; } bool isGreater(int x, int y) { // Two conditions // i) r[x] = r[x+1] = ... = r[y-1] = 0 int s0 = rpref[y] - rpref[x]; if (s0 == 0) return true; // ii) r[y] = ... = r[n-1] = 1 and r[0] = ... = r[x-1] = 1 int s1 = rpref[n] - rpref[y+1]; s1 += rpref[x] - rpref[0]; int l1 = (n-1-y); l1 += x; if (l1 == s1) return true; return false; } // 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) { if (isGreater(x, y)) { return 1; } else if (isSmaller(x, y)) { return -1; } else { return 0; } } #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...