oj.uz

Submission #677681

# Submission time Handle Problem Language Result Execution time Memory
677681 2023-01-04T07:11:04 Z Cross_Ratio Seesaw (JOI22_seesaw) C++14
100 / 100
 256 ms 35136 KB 
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
int A[200005];
int B[200005];
int N;
vector<double> V[200005];
int sum(int x, int y) {
    return B[y] - (x?B[x-1]:0);
}
typedef pair<int,int> P;
typedef pair<double, pair<int,int>> PP;
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> A[i];
    for(i=0;i<N;i++) {
        B[i] = (i?B[i-1]:0)+A[i];
    }
    int s1 = 0, e1 = N-1, s2 = 0, e2 = N-1;
    V[N].push_back((double)B[N-1]/N);
    for(i=N-1;i>=1;i--) {
        e1--, s2++;
        while(e1+1<N&&(double)sum(s1+1, e1+1)/i<=(double)B[N-1]/N) {
            s1++, e1++;
        }
        while(s2-1>=0&&(double)sum(s2-1, e2-1)/i>=(double)B[N-1]/N) {
            s2--, e2--;
        }
        //assert(s2>=s1);
        //if(s2<s1) s2 = s1, e2 = e1;
        /*if(sum(s1+1, e1)*N <= B[N-1]*i) {
            s1++;
        }
        else e1--;
        if(sum(s2, e2-1)*N >= B[N-1]*i) {
            e2--;
        }
        else s2++;*/
        //assert(s1+1>=s2);
        /*assert(sum(s1, e1) * N <= B[N-1] * i);
        assert(sum(s2, e2) * N >= B[N-1] * i);*/
        for(j=s1;j<=s2;j++) {
            V[i].push_back((double)sum(j, j+i-1) / i);
        }
    }
    set<PP> S;
    for(i=1;i<=N;i++) {
        S.insert(PP(V[i][0], P(i, 0)));
    }
    double ans = 1e9;
    while(true) {
        double mi = S.begin()->first;
        double ma = S.rbegin()->first;
        ans = min(ans, ma - mi);
        PP k = *S.begin();
        auto it = S.begin();
        S.erase(it);
        int k1 = k.second.first, k2 = k.second.second;
        if(k2+1>=V[k1].size()) break;
        S.insert(PP(V[k1][k2+1], P(k1, k2)));
    }
    cout << fixed << setprecision(15) << ans;
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:64:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         if(k2+1>=V[k1].size()) break;
      |            ~~~~^~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

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

Subtask #3
33.0 / 33.0

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

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 5052 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 5 ms 5204 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 4 ms 5204 KB Output is correct
12 Correct 240 ms 33176 KB Output is correct
13 Correct 246 ms 35112 KB Output is correct
14 Correct 256 ms 35028 KB Output is correct
15 Correct 247 ms 35136 KB Output is correct
16 Correct 242 ms 35108 KB Output is correct