제출 #303121

#제출 시각아이디문제언어결과실행 시간메모리
303121tutis식물 비교 (IOI20_plants)C++17
5 / 100
111 ms5984 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; vector<int>k0, k1; int K, n; vector<int>A; struct ST { int l, r; pair<int, int> mn; int del = 0; ST *left, *right; ST(int l, int r, vector<int>&a): l(l), r(r) { if (l < r) { left = new ST(l, (l + r) / 2, a); right = new ST((l + r) / 2 + 1, r, a); mn = min(left->mn, right->mn); } else mn = {a[l], l}; } void fix() { if (l == r) { mn.first += del; del = 0; } else { mn.first += del; left->del += del; right->del += del; del = 0; } } void add(int x, int y, int w) { if (x <= l && r <= y) { del += w; return fix(); } fix(); if (r < x || y < l) return; left->add(x, y, w); right->add(x, y, w); mn = min(left->mn, right->mn); } }; void init(int k, vector<int> r) { K = k; n = r.size(); if (k == 2) { k0 = k1 = vector<int>(n, 0); for (int t = 0; t < 2; t++) for (int i = n - 1; i >= 0; i--) { if (r[i] == 0) k0[i] = 1 + k0[(i + 1) % n]; else k1[i] = 1 + k1[(i + 1) % n]; } return; } if (2 * k > n) { ST medis(0, n - 1, r); auto add = [&](int x, int y, int w) { while (y >= n) { x -= n; y -= n; } while (x < 0) { x += n; y += n; } if (y < n) { medis.add(x, y, w); } else { medis.add(x, n - 1, w); medis.add(0, y - n, w); } }; for (int i = 0; i < n; i++) if (r[i] == 0) add(i + 1, i + k - 1, 1); A = vector<int>(n, -1); for (int tt = 0; tt < n; tt++) { int i = medis.mn.second; add(i + 1, i + k - 1, -1); add(i - (k - 1), i - 1, -1); A[i] = tt; add(i, i, n + 10000); r[i] = n + 100; } return; } } int compare_plants(int x, int y) { assert(x < y); if (K == 2) { if (k0[x] >= y - x) return 1; if (k1[x] >= y - x) return -1; if (k0[y] >= n - y + x) return -1; if (k1[y] >= n - y + x) return 1; return 0; } if (!A.empty()) { if (A[x] < A[y]) return 1; else return -1; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:50:13: warning: 'medis.ST::right' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |   right->add(x, y, w);
      |   ~~~~~~~~~~^~~~~~~~~
plants.cpp:73:6: note: 'medis.ST::right' was declared here
   73 |   ST medis(0, n - 1, r);
      |      ^~~~~
plants.cpp:49:12: warning: 'medis.ST::left' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   left->add(x, y, w);
      |   ~~~~~~~~~^~~~~~~~~
plants.cpp:73:6: note: 'medis.ST::left' was declared here
   73 |   ST medis(0, n - 1, r);
      |      ^~~~~
#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...