oj.uz

Submission #624861

# Submission time Handle Problem Language Result Execution time Memory
624861 2022-08-08T22:26:59 Z KKT89 Seesaw (JOI22_seesaw) C++17
100 / 100
 274 ms 21060 KB 
#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

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.0 / 1.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 2 ms 464 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 500 KB Output is correct
11 Correct 2 ms 464 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 2 ms 464 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 500 KB Output is correct
11 Correct 2 ms 464 KB Output is correct
12 Correct 254 ms 20956 KB Output is correct
13 Correct 262 ms 21060 KB Output is correct
14 Correct 274 ms 21052 KB Output is correct
15 Correct 256 ms 21048 KB Output is correct
16 Correct 261 ms 21052 KB Output is correct