Submission #677961

#	Time	Username	Problem	Language	Result	Execution time	Memory
677961		qwerasdfzxcl	Seesaw (JOI22_seesaw)	C++17	100 / 100	194 ms	17880 KiB

seesaw

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Frac{
    ll a, b;
    Frac(){}
    Frac(ll _a, ll _b): a(_a), b(_b) {}

    long double ch()const{return (long double) a / b;}

    bool operator < (const Frac &F) const{
        return (__int128)a * F.b < (__int128)b * F.a;
    }
};

int n, a[200200], idx[200200];
set<pair<Frac, int>> st;
ll S[200200];

Frac val(int l, int r){return Frac(S[r] - S[l-1], r-l+1);}

int main(){
    scanf("%d", &n);
    for (int i=1;i<=n;i++) scanf("%d", a+i);
    for (int i=1;i<=n;i++) S[i] = S[i-1] + a[i];

    for (int d=0;d<=n-1;d++){
        int l = 1, r = n-d;
        idx[d] = 1;

        while(l<=r){
            int m = (l+r)>>1;
            if (val(m, m+d) < val(1, n)) idx[d] = m, l = m+1;
            else r = m-1;
        }

        st.emplace(val(idx[d], idx[d]+d), d);
    }

    long double ans = 1e18;

    while(!st.empty()){
        ans = min(ans, st.rbegin()->first.ch() - st.begin()->first.ch());

        auto [x, d] = *st.begin();
        st.erase(st.begin());
        if (idx[d]+1+d > n) break;

        st.emplace(val(idx[d]+1, idx[d]+d+1), d);
    }

    printf("%.15Lf\n", ans);
    return 0;
}

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
seesaw.cpp:25:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     for (int i=1;i<=n;i++) scanf("%d", a+i);
      |                            ~~~~~^~~~~~~~~~~

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