oj.uz

Submission #677961

# Submission time Handle Problem Language Result Execution time Memory
677961 2023-01-04T18:07:23 Z qwerasdfzxcl Seesaw (JOI22_seesaw) C++17
100 / 100
 194 ms 17880 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 194 ms 15936 KB Output is correct
13 Correct 168 ms 17876 KB Output is correct
14 Correct 164 ms 17788 KB Output is correct
15 Correct 169 ms 17864 KB Output is correct
16 Correct 157 ms 17880 KB Output is correct