oj.uz

Submission #753777

# Submission time Handle Problem Language Result Execution time Memory
753777 2023-06-06T02:03:10 Z pavement Seesaw (JOI22_seesaw) C++17
100 / 100
 328 ms 38232 KB 
#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

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

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 340 KB Output is correct
3 Correct 1 ms 336 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 340 KB Output is correct
3 Correct 1 ms 336 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 336 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 340 KB Output is correct
3 Correct 1 ms 336 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 336 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 736 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 732 KB Output is correct
11 Correct 2 ms 724 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 340 KB Output is correct
3 Correct 1 ms 336 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 336 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 736 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 732 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 294 ms 38172 KB Output is correct
13 Correct 325 ms 38108 KB Output is correct
14 Correct 305 ms 38232 KB Output is correct
15 Correct 302 ms 38216 KB Output is correct
16 Correct 328 ms 38148 KB Output is correct