oj.uz

Submission #752769

# Submission time Handle Problem Language Result Execution time Memory
752769 2023-06-03T19:53:04 Z IBory Seesaw (JOI22_seesaw) C++14
100 / 100
 183 ms 50772 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MAX = 200007;
ll S[MAX], on[MAX];
vector<pair<double, int>> P;
map<pii, int> check;

double Center(int L, int R) {
	return (S[R] - S[L - 1]) / (double)(R - L + 1);
}

void DFS(int L, int R, double init) {
	if (check.find({ L, R }) != check.end()) return;
	check[{L, R}] = 1;
	P.emplace_back(Center(L, R), R - L + 1);
	if (L == R) return;
	double CL = Center(L, R - 1), CR = Center(L + 1, R);
	if (init <= CR) DFS(L, R - 1, init);
	if (CL <= init) DFS(L + 1, R, init);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> S[i];
		S[i] += S[i - 1];
	}

	int g = N / 2;
	double init = S[N] / (double)N;
	DFS(1, N, init);
	sort(P.begin(), P.end());

	double ans = 1e18;
	int cnt = 0, R = 0;
	on[P[0].second] = 1;
	for (int L = 0; L < P.size(); ++L) {
		while (R + 1 < P.size() && cnt != N - 1) {
			int t = P[++R].second;
			if (t != 1 && on[t - 1] && !on[t]) cnt++;
			if (t != N && on[t + 1] && !on[t]) cnt++;
			on[t]++;
		}
		if (cnt == N - 1) ans = min(ans, P[R].first - P[L].first);
		int t = P[L].second;
		on[t]--;
		if (t != 1 && on[t - 1] && !on[t]) cnt--;
		if (t != N && on[t + 1] && !on[t]) cnt--;
	}

	cout.precision(12);
	cout << fixed << ans;
	return 0;
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int L = 0; L < P.size(); ++L) {
      |                  ~~^~~~~~~~~~
seesaw.cpp:43: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]
   43 |   while (R + 1 < P.size() && cnt != N - 1) {
      |          ~~~~~~^~~~~~~~~~
seesaw.cpp:34:6: warning: unused variable 'g' [-Wunused-variable]
   34 |  int g = N / 2;
      |      ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 324 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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 724 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 174 ms 50772 KB Output is correct
13 Correct 183 ms 50708 KB Output is correct
14 Correct 168 ms 50664 KB Output is correct
15 Correct 183 ms 50768 KB Output is correct
16 Correct 171 ms 50752 KB Output is correct