Submission #1055513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055513		juliany2	Seesaw (JOI22_seesaw)	C++17	100 / 100	53 ms	13776 KiB

seesaw

#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) {
      |                ~~~~~~^~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33