Submission #712184

#	Time	Username	Problem	Language	Result	Execution time	Memory
712184		Mery2005	Seesaw (JOI22_seesaw)	C++14	0 / 100	1 ms	308 KiB

seesaw

#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include <list>
#include <string>
#include <unordered_map>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <iomanip>
 
using namespace std;
 
void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

const int N = 2e5+5;
long double w[N] , s[N];

void solve(){
   long double L = 0 , R = 0 ;
   int n;
   cin >> n;
   int l = 1 , r = n , l1 = 0 , r1 = 0;
   for(int i = 1 ; i <= n ; i++){
       cin >> w[i];
       s[i] = s[i-1] + w[i];
   }
   L = s[n]/n;
   R = s[n]/n;
   double mn = 1e9;
   for(int i = 1 ; i <= n ; i++){
        if(abs(L - w[i]) <= mn){
            mn = abs(L - w[i]);
            l1 = i;
            r1 = i;
        }
    }
    L = min(L , w[l1]);
    R = max(R , w[l1]);
    while(l < l1 && r > r1){
        long double s1 = (s[r-1] - s[l-1]) / (r-l);
        long double s2 = (s[r] - s[l]) / (r-l);
        if((s1 >= L && s1 <= R) && (s2 >= L && s2 <= R)){
            if(min(abs(L - s1) , abs(R - s1)) <= min(abs(L - s2) , abs(R - s2))){
                r--;
            }
            else{
                l++;
            }
        }
        else if((s1 >= L && s1 <= R)){
            r--;
        }
        else if((s2 >= L && s2 <= R)){
            l++;
        }
        else if(min(abs(L - s1) , abs(R - s1)) <= min(abs(L - s2) , abs(R - s2))){
            r--;
            L = min(L , s1);
            R = max(R , s1);
        }
        else{
            l++;
            L = min(L , s2);
            R = min(R , s2);
        }
        long double s11 = -1000000000;
        long double s22 = -1000000000;
        if(r1+1 <= n){
            s11 = (s[r1+1] - s[l1-1]) / (r1-l1+2);
        }
        if(l1 >= 2){
            s22 = (s[r1] - s[l1-2]) / (r1-l1+2);
        }
        if((s11 >= L && s11 <= R) && (s22 >= L && s22 <= R)){
            if(min(abs(L - s11) , abs(R - s11)) <= min(abs(L - s22) , abs(R - s22))){
                r1++;
            }
            else{
                l1--;
            }
        }
        else if((s11 >= L && s11 <= R)){
            r1++;
        }
        else if((s22 >= L && s22 <= R)){
            l1--;
        }
        else if(min(abs(L - s11) , abs(R - s11)) <= min(abs(L - s22) , abs(R - s22))){
            r1++;
            L = min(L , s11);
            R = max(R , s11);
        }
        else{
            l1--;
            L = min(L , s22);
            R = max(R , s22);
        }
    }
    cout << setprecision(9) << (R-L) <<  endl;
}
 
int main() {
    solve();
    return 0;
}

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