Submission #624861

#	Time	Username	Problem	Language	Result	Execution time	Memory
624861		KKT89	Seesaw (JOI22_seesaw)	C++17	100 / 100	274 ms	21060 KiB

seesaw

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <sstream>
#include <utility>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <array>
#include <bitset>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

double ave(ll sum,ll n){
    return sum*1.0/n;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<ll> a(n);
    vector<ll> sum(n+1);
    for(int i=0;i<n;i++){
        cin >> a[i];
        sum[i+1] = sum[i]+a[i];
    }
    auto mid = ave(sum[n],n);
    vector<pair<double,int>> v;
    v.push_back({mid,n});
    for(int i=n-1;i>=1;i--){
        int l = 1, r = n-i+2;
        while(r-l>1){
            int m = (l+r)/2;
            if(ave(sum[m+i-1]-sum[m-1],i) <= mid){
                l = m;
            }
            else{
                r = m;
            }
        }
        v.push_back({ave(sum[l+i-1]-sum[l-1],i),i});
        v.push_back({ave(sum[l+i]-sum[l],i),i});
    }
    sort(v.begin(), v.end());
    map<int,int> mp;
    double res = 1e18;
    int r = 0;
    for(int i=0;i<v.size();i++){
        while(r<v.size() and mp.size() < n){
            mp[v[r].second]++;
            r++;
        }
        res = min(res,v[r-1].first-v[i].first);
        mp[v[i].second]--;
        if(mp[v[i].second] == 0){
            if(v[i].second == n) break;
            mp.erase(mp.find(v[i].second));
        }
    }
    printf("%.9f\n",res);
}

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
seesaw.cpp:72:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         while(r<v.size() and mp.size() < n){
      |               ~^~~~~~~~~
seesaw.cpp:72:40: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |         while(r<v.size() and mp.size() < n){
      |                              ~~~~~~~~~~^~~

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