제출 #1127400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127400		vladilius	Seesaw (JOI22_seesaw)	C++20	0 / 100	0 ms	324 KiB

seesaw

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pdi = pair<double, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> a(n + 1);
    vector<ll> p(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i];
        p[i] = p[i - 1] + a[i];
    }
    
    auto get = [&](int l, int r){
        return 1.0 * (p[r] - p[l - 1]) / (r - l + 1);
    };
    
    double A = get(1, n);
    
    vector<pii> all = {{1, n}};
    
    int l = 1, r = n, dx = 1, dy = 0;
    while (l < r){
        l += dx; r -= dy;
        if (get(l, r) > A){
            swap(dx, dy);
        }
        all.pb({l, r});
    }
    
    l = 1; r = n; dx = 0; dy = 1;
    while (l < r){
        l += dx; r -= dy;
        if (get(l, r) > A){
            swap(dx, dy);
        }
        all.pb({l, r});
    }
    
    auto cmp = [&](pii x, pii y){
        return get(x.ff, x.ss) < get(y.ff, y.ss);
    };
    
    sort(all.begin(), all.end(), cmp);
    
    auto d = [&](int i){
        return get(all[i].ff, all[i].ss);
    };
    
    vector<int> f(n);
    int j = 0, cnt = 0;
    double out = 1e9 + 1;
    for (int i = 0; i < all.size(); i++){
        while (cnt < n && j < all.size()){
            int k = all[j].ss - all[j].ff;
            if (!f[k]) cnt++;
            f[k]++;
            j++;
        }
        
        if (cnt == n) out = min(out, d(j - 1) - d(i));
        
        int k = all[i].ss - all[i].ff;
        f[k]--;
        if (!f[k]) cnt--;
    }
    
    cout<<fixed<<setprecision(12)<<out<<"\n";
}

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