Submission #1197603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197603		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 bary = [&](int i, int j){
        return (S[j] - S[i-1]) / (j - i + 1);
    };

    auto can = [&](ld w){
        ld mu0 = S[N] / N;
        array<pair<ld,bool>,2> trials = {{
            {mu0 - w, true},
            {mu0,     false}
        }};
        for(auto [L, rightFirst] : trials){
            ld low = L, high = L + w;
            int i = 1, j = N;
            bool ok = true;
            while(i < j){
                ld cL = bary(i+1, j);
                ld cR = bary(i, j-1);

                bool canL = (low <= cL && cL <= high);
                bool canR = (low <= cR && cR <= high);

                if(!canL && !canR){
                    ok = false;
                    break;
                }
                if(canL && canR){
                    if(rightFirst){
                        low  = max(low, cR - w);
                        high = min(high, cR);
                        j--;
                    } else {
                        low  = max(low, cL - w);
                        high = min(high, cL);
                        i++;
                    }
                }
                else if(canL){
                    low  = max(low, cL - w);
                    high = min(high, cL);
                    i++;
                }
                else {
                    low  = max(low, cR - w);
                    high = min(high, cR);
                    j--;
                }
            }
            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