Submission #753777

#	Time	Username	Problem	Language	Result	Execution time	Memory
753777		pavement	Seesaw (JOI22_seesaw)	C++17	100 / 100	328 ms	38232 KiB

seesaw

#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;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, A[200005], P[200005];
ld ans = numeric_limits<ld>::infinity();
multiset<ld> ss;
vector<tuple<ld, int, ld> > ev;

ld f(int l, int r) {
	return (ld)(P[r] - P[l - 1]) / (r - l + 1);
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		P[i] = P[i - 1] + A[i];
	}
	for (int i = 1; i < N; i++) {
		int lo = 1, hi = N - i + 1, ans = -1;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			if (f(mid, mid + i - 1) <= f(1, N)) {
				ans = mid;
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		}
		assert(ans != -1);
		ev.eb(f(ans, ans + i - 1), 0, f(ans + 1, ans + i));
		ev.eb(f(ans + 1, ans + i), 1, -1);
		ss.insert(f(ans, ans + i - 1));
	}
	ss.insert(f(1, N));
	sort(ev.begin(), ev.end());
	for (auto [v, t, oth] : ev) {
		if (v > f(1, N)) break;
		ans = min(ans, *ss.rbegin() - v);
		ss.erase(ss.find(v));
		if (t == 1) break;
		else ss.insert(oth);
	}
	cout << fixed << setprecision(10) << ans << '\n';
}

Compilation message (stderr)

seesaw.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main() {
      | ^~~~

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