oj.uz

Submission #854499

# Submission time Handle Problem Language Result Execution time Memory
854499 2023-09-27T18:36:13 Z vjudge1 Seesaw (JOI22_seesaw) C++17
100 / 100
 435 ms 18032 KB 
#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() {
                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 (long double)e.x / e.y < (long double)f.x / f.y; }
        friend bool operator<=(const fraction_t& e, const fraction_t& f) { return (long double)e.x / e.y <= (long double)f.x / f.y; }
        friend bool operator==(const fraction_t& e, const fraction_t& f) { return e.x == f.x && e.y == f.y; }
        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) {
                        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

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 2 ms 552 KB Output is correct
11 Correct 2 ms 604 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 2 ms 552 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 418 ms 15916 KB Output is correct
13 Correct 409 ms 17844 KB Output is correct
14 Correct 435 ms 17824 KB Output is correct
15 Correct 411 ms 17900 KB Output is correct
16 Correct 405 ms 18032 KB Output is correct