oj.uz

Submission #748435

# Submission time Handle Problem Language Result Execution time Memory
748435 2023-05-26T09:35:33 Z MridulAhi Seesaw (JOI22_seesaw) C++17
100 / 100
 238 ms 24216 KB 
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
                // http://xorshift.di.unimi.it/splitmix64.c
                x += 0x9e3779b97f4a7c15;
                x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
                x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
                return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
                static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
                return splitmix64(x + FIXED_RANDOM);
        }
};
//auto rng = std::default_random_engine {};

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;


#define rep(i, a, b) for(int i = a; i < b; i++)
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
#define int long long

const ll mod = 998244353;
const ll INF = 1e18;

/* ----------------------------------------------------- GO DOWN ---------------------------------------------------------------------- */




signed main() {

        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        int n;
        cin >> n;
        long double a[n];
        for (int i = 0; i < n; i++) cin >> a[i];

        set<pair<long double, int>> s;

        long double ans = INF;
        long double mid = 0;
        long double sum = 0;
        for (auto u : a) sum += u;
        mid = sum / n;

        long double nw[n - 1];
        int cl = 0, cr = n - 1;
        for (int i = 1; i < n; i++) {
                if ((sum - a[cl]) / (n - i) < mid) {
                        sum -= a[cl];
                        cl++;
                        nw[i] = (sum + a[cr + 1] - a[cl]) / (n - i);
                }
                else {
                        sum -= a[cr];
                        cr--;
                        nw[i] = (sum + a[cr + 1] - a[cl]) / (n - i);
                }
                s.insert({sum / (n - i), i});
        }
        
        s.insert({mid, 0});

        while (s.begin()->second != 0) {
                ans = min(ans, s.rbegin()->first - s.begin()->first);
                auto [val, i] = *s.begin();
                s.erase(s.begin());
                s.insert({nw[i], i});
        }

        ans = min(ans, s.rbegin()->first - s.begin()->first);

        cout << fixed << setprecision(15);

        cout << ans;

}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 1 ms 340 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 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 3 ms 468 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 237 ms 24148 KB Output is correct
13 Correct 226 ms 24216 KB Output is correct
14 Correct 216 ms 24148 KB Output is correct
15 Correct 238 ms 24152 KB Output is correct
16 Correct 217 ms 24128 KB Output is correct