Submission #854498

#TimeUsernameProblemLanguageResultExecution timeMemory
854498vjudge1Seesaw (JOI22_seesaw)C++17
67 / 100
343 ms15948 KiB
#include <bits/stdc++.h> using namespace std; class fraction_t { public: int64_t x, y; // x / y, normalized to y > 0 if x != 0 and y = 1 if x = 0 void fix() { assert(y && "Your Denominator Equal 0"); int64_t d = __gcd(abs(x), y); x /= d; y /= d; } fraction_t(const int64_t& x = 0, const int64_t& y = 1) : x(x), y(y) { fix(); } friend bool operator<(const fraction_t& e, const fraction_t& f) { return e.x * f.y < e.y * f.x; } friend bool operator<=(const fraction_t& e, const fraction_t& f) { return e.x * f.y <= e.y * f.x; } friend bool operator==(const fraction_t& e, const fraction_t& f) { return e.x * f.y == e.y * f.x; } friend bool operator!=(const fraction_t& e, const fraction_t& f) { return e.x * f.y != e.y * f.x; } friend bool operator>(const fraction_t& e, const fraction_t& f) { return e.x * f.y > e.y * f.x; } friend bool operator>=(const fraction_t& e, const fraction_t& f) { return e.x * f.y >= e.y * f.x; } friend ostream& operator<<(ostream& out, const fraction_t& f) { out << setprecision(11) << fixed << ((double)f.x) / f.y; return out; } }; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<int64_t> pref(n + 1, 0); for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i]; fraction_t c(pref[n] - pref[0], n); set<pair<fraction_t, int>> s; vector<int> nxt(n, -1); for (int i = n - 1; i > 0; i--) { int l = 0, r = n - i, fl; while (l <= r) { int mid = l + r >> 1; if (fraction_t(pref[mid + i] - pref[mid], i) <= c) { fl = mid; l = mid + 1; } else { r = mid - 1; } } fraction_t f(pref[fl + i] - pref[fl], i); if (f != c) { if (fl + 1 + i <= n) nxt[i] = fl + 1; } s.emplace(f, i); } s.emplace(c, 0); long double res = 1e18; while (true) { auto [f, i] = *s.begin(); auto a = s.rbegin()->first; auto b = s.begin()->first; long double aa = (long double)a.x / a.y; long double bb = (long double)b.x / b.y; res = min(res, aa - bb); s.erase(s.begin()); if (nxt[i] == -1) break; s.emplace(fraction_t(pref[nxt[i] + i] - pref[nxt[i]], i), i); nxt[i] = -1; } cout << fixed << setprecision(11) << res; }

Compilation message (stderr)

seesaw.cpp: In function 'int32_t main()':
seesaw.cpp:46:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |                         int mid = l + r >> 1;
      |                                   ~~^~~
seesaw.cpp:55:52: warning: 'fl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |                 fraction_t f(pref[fl + i] - pref[fl], i);
      |                                                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...