oj.uz

Submission #677637

# Submission time Handle Problem Language Result Execution time Memory
677637 2023-01-04T05:20:14 Z Cross_Ratio Seesaw (JOI22_seesaw) C++14
1 / 100
 1 ms 324 KB 
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
double INF = 2 * 1e9;
int A[200005];
int N;
double get_val(double L) {
    int s = 0, e = N-1;
    double sum = 0;
    for(int i = 0; i < N; i++) sum += A[i];
    int val = N;
    double ma = sum / val;
    while(s<=e) {
        if(sum / val < L) return INF;
        while(e>=s && sum - A[e] >= L * (val-1)) {
            sum -= A[e];
            e--;
            val--;
            if(val != 0) ma = max(ma, sum / val);
            if(val!=0 && sum / val < L) return INF;
        }
        if(s>e) break;
        sum -= A[s];
        s++;
        val--;
        if(val!=0&&sum/val<L) return INF;
        if(val!=0) ma = max(ma, sum / val);
    }
    return ma - L;
}
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];
    double mi = INF;
    double s = 0, e = 1e9;
    int cnt = 150;
    while(cnt--) {
        double s1 = (2*s+e)/3;
        double s2 = (s+2*e)/3;
        double v1 = get_val(s1), v2 = get_val(s2);
        mi = min(mi, v1);
        mi = min(mi, v2);
        if(v1 <= v2) {
            e = s2;
        }
        else {
            s = s1;
        }
        /*cout << s1 << " : " << v1 << '\n';
        cout << s2 << " : " << v2 << '\n';
        cout <<s << ' ' << e << '\n';*/
    }
    cout << fixed << setprecision(15) << mi;
    //cout << '\n' << get_val(0.5) << ' ' << get_val(0.75) << ' ' << get_val(1) << ' ' <<get_val(1.25) << ' ' << get_val(1.5);
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:38:12: warning: unused variable 'j' [-Wunused-variable]
   38 |     int i, j;
      |            ^

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 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -