Submission #1055513

#TimeUsernameProblemLanguageResultExecution timeMemory
1055513juliany2Seesaw (JOI22_seesaw)C++17
100 / 100
53 ms13776 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define all(x) (x).begin(), (x).end() // path from (1, n) to any (i, i) // as long as all diags have at least one valid theres always a valid path // can connect any two of these points with a right/down path, which is monotic increasing int main() { cin.tie(0)->sync_with_stdio(false); int n; cin >> n; vector<ll> a(n + 1), pref(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } double avg = (double) pref[n] / n; vector<pair<double, int>> b; b.push_back({avg, n}); for (int len = 1; len < n; len++) { int lo = len, hi = n; while (lo < hi) { int mid = (lo + hi + 1) / 2; if ((double) (pref[mid] - pref[mid - len]) / len < avg) lo = mid; else hi = mid - 1; } b.push_back({(double) (pref[lo] - pref[lo - len]) / len, len}); b.push_back({(double) (pref[lo + 1] - pref[lo + 1 - len]) / len, len}); } sort(all(b)); vector<int> cnt(n + 1); int valid = 0; double ans = 1e18; int r = -1; for (int l = 0; l < b.size(); l++) { while (r + 1 < b.size() && valid < n) { r++; if (!cnt[b[r].second]++) valid++; } if (valid == n) ans = min(ans, b[r].first - b[l].first); if (!--cnt[b[l].second]) valid--; } cout << fixed << setprecision(15) << ans << '\n'; return 0; }

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int l = 0; l < b.size(); l++) {
      |                     ~~^~~~~~~~~~
seesaw.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         while (r + 1 < b.size() && valid < n) {
      |                ~~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...