Submission #633568

#	Time	Username	Problem	Language	Result	Execution time	Memory
633568		Astrayt	Seesaw (JOI22_seesaw)	C++14	0 / 100	1 ms	212 KiB

seesaw

//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define N 100005

void solve(){
    int n, s = 0, m1, m2, k; cin >> n;
    vector<int> v(n);
    for(auto &x:v) cin >> x, s += x;
    double bary = (double) s / (double) n, l, r, ans = 1e9;
    l = r = bary;
    m1 = v[n / 2], m2 = v[(n - 1) / 2];
    k = n;
    int he = 0, ta = n - 1, tmp = s;
    while(he != ta){
        if(bary < m1){
            tmp -= v[he]; he++; --k;
            bary = (double)tmp / (double)k;
            r = max(r, bary);
        }else if(bary > m1){
            tmp -= v[ta]; ta--; --k;
            bary = (double)tmp / (double)k;
            l = min(l, bary);
        }else{
            if(abs(m1 - v[he]) >= abs(m1 - v[ta])){
                s -= v[he]; he++; --k;
                bary = (double)tmp / (double)k;
                r = max(r, bary);
            }else{
                tmp -= v[ta]; ta--; --k;
                bary = (double)tmp / (double)k;
                l = min(l, bary);
            }
        }
    }
    ans = min(ans, r - l);
    k = n;
    he = 0, ta = n - 1;
    tmp = s;
    bary = (double) s / (double) n;
    l = r = bary;
    while(he != ta){
        if(bary < m2){
            tmp -= v[he]; he++; --k;
            bary = (double)tmp / (double)k;
            r = max(r, bary);
        }else if(bary > m2){
            tmp -= v[ta]; ta--; --k;
            bary = (double)tmp / (double)k;
            l = min(l, bary);
        }else{
            if(abs(m2 - v[he]) >= abs(m2 - v[ta])){
                s -= v[he]; he++; --k;
                bary = (double)tmp / (double)k;
                r = max(r, bary);
            }else{
                tmp -= v[ta]; ta--; --k;
                bary = (double)tmp / (double)k;
                l = min(l, bary);
            }
        }
    }
    ans = min(ans, r - l);
    cout << fixed << setprecision(9) << ans << '\n';
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}

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