oj.uz

Submission #777010

# Submission time Handle Problem Language Result Execution time Memory
777010 2023-07-08T13:35:31 Z Rafi22 Seesaw (JOI22_seesaw) C++14
100 / 100
 119 ms 13700 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=200007;

ll a[N];
ll P[N];

bool cmp(pair<ll,ll>l,pair<ll,ll>r)
{
    return (ld)l.st/(ld)l.nd<(ld)r.st/(ld)r.nd;
}

int cnt[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        P[i]=P[i-1]+a[i];
    }
    vector<pair<ll,ll>>V;
    V.pb({P[n],n});
    for(int k=1;k<n;k++)
    {
        int l=1,r=n-k+1,sr,p;
        while(l<=r)
        {
            sr=(l+r)/2;
            if((ld)(P[sr+k-1]-P[sr-1])/(ld)k<=(ld)P[n]/(ld)n)
            {
                p=sr;
                l=sr+1;
            }
            else r=sr-1;
        }
        V.pb({P[p+k-1]-P[p-1],k});
        if(p+k<=n) V.pb({P[p+k]-P[p],k});
    }
    sort(all(V),cmp);
    ld ans=inf;
    int j=0,ile=0;
    for(int i=0;i<sz(V);i++)
    {
        while(j<sz(V)&&ile<n)
        {
            cnt[V[j].nd]++;
            if(cnt[V[j].nd]==1) ile++;
            j++;
        }
        if(ile==n)
        {
            ans=min(ans,(ld)V[j-1].st/(ld)V[j-1].nd-(ld)V[i].st/(ld)V[i].nd);
        }
        cnt[V[i].nd]--;
        if(cnt[V[i].nd]==0) ile--;
    }
    cout<<fixed<<setprecision(9)<<ans;

    return 0;
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:57:36: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |         if(p+k<=n) V.pb({P[p+k]-P[p],k});
      |                                 ~~~^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 288 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 1 ms 340 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 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 1 ms 340 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 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 1 ms 340 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 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 118 ms 11748 KB Output is correct
13 Correct 117 ms 13696 KB Output is correct
14 Correct 118 ms 13636 KB Output is correct
15 Correct 119 ms 13696 KB Output is correct
16 Correct 117 ms 13700 KB Output is correct