Submission #748435

#	Time	Username	Problem	Language	Result	Execution time	Memory
748435		MridulAhi	Seesaw (JOI22_seesaw)	C++17	100 / 100	238 ms	24216 KiB

seesaw

//#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 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33