Submission #1197600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197600		primo	Seesaw (JOI22_seesaw)	C++20	0 / 100	0 ms	324 KiB

seesaw

#include <bits/stdc++.h>
using namespace std;
using ld = long double;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<ld> A(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    sort(A.begin(), A.end());

    vector<ld> S(N+1, 0);
    for(int i = 1; i <= N; i++){
        S[i] = S[i-1] + A[i-1];
    }

    auto can = [&](ld w){
        ld mu0 = S[N] / N;
        array<ld,2> Ls = { mu0 - w, mu0 };
        for(ld L : Ls){
            int i = 1, j = N;
            bool ok = true;
            while(i < j){
                ld cL = (S[j] - S[i])   / (j - i);
                ld cR = (S[j-1] - S[i-1]) / (j - i);
                if (L <= cL && cL <= L + w) {
                    i++;
                }
                else if (L <= cR && cR <= L + w) {
                    j--;
                }
                else {
                    ok = false;
                    break;
                }
            }
            if(ok) return true;
        }
        return false;
    };

    ld lo = 0, hi = A.back() - A.front();
    for(int it = 0; it < 80; it++){
        ld mid = (lo + hi) / 2;
        if(can(mid)) hi = mid;
        else        lo = mid;
    }

    cout << fixed << setprecision(10) << hi << "\n";
    return 0;
}

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