Submission #677644

#	Time	Username	Problem	Language	Result	Execution time	Memory
677644		Cross_Ratio	Seesaw (JOI22_seesaw)	C++14	1 / 100	1 ms	212 KiB

seesaw

#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;
    int sum = 0;
    for(int i = 0; i < N; i++) sum += A[i];
    int val = N;
    double ma = 1.0*sum / val;
    while(s<=e) {
        if(sum < L*val) return INF;
        while(e>=s && sum - A[e] >= L * (val-1)) {
            sum -= A[e];
            e--;
            val--;
            if(val != 0) ma = max(ma, (double)sum / val);
            if(val!=0 && sum  < L*val) return INF;
        }
        if(s>e) break;
        sum -= A[s];
        s++;
        val--;
        if(val!=0&&sum<L*val) return INF;
        if(val!=0) ma = max(ma, (double)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;
    int sum = 0;
    for(i=0;i<N;i++) sum += A[i];
    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 >= 1.5 * 1e9) {
            //cout << s << ' ' << e << '\n';
            //cout << s1 << " : Limited\n";
            e = s1;
            continue;
        }
        if(v2 >= 1.5 * 1e9) {
            //cout << s << ' ' << e << '\n';
            //cout << s2 << " : Limited\n";
            e = s2;
            continue;
        }
        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 (stderr)

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

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