oj.uz

Submission #719176

# Submission time Handle Problem Language Result Execution time Memory
719176 2023-04-05T15:03:59 Z rainboy Seesaw (JOI22_seesaw) C
100 / 100
 97 ms 8460 KB 
#include <stdio.h>

#define N	200000

double min(double a, double b) { return a < b ? a : b; }
double max(double a, double b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

double xx[N], yy[N];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (xx[hh[j]] == xx[h])
				j++;
			else if (xx[hh[j]] < xx[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int main() {
	static int aa[N], hh[N];
	static long long ss[N + 1];
	int n, m, h, i, k, lower, upper;
	double y, ans;

	scanf("%d", &n);
	ss[0] = 0;
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		ss[i + 1] = ss[i] + aa[i];
	}
	m = 0;
	for (k = 1; k < n; k++) {
		lower = 0, upper = n - k + 1;
		while (upper - lower > 1) {
			i = (lower + upper) / 2;
			if ((double) (ss[i + k] - ss[i]) / k <= (double) ss[n] / n)
				lower = i;
			else
				upper = i;
		}
		i = lower;
		if ((double) (ss[i + k] - ss[i]) / k == (double) ss[n] / n)
			continue;
		xx[m] = (double) (ss[i + k] - ss[i]) / k, yy[m] = (double) (ss[i + 1 + k] - ss[i + 1]) / k, m++;
	}
	if (m == 0) {
		printf("0\n");
		return 0;
	}
	for (h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	y = (double) ss[n] / n;
	ans = y - xx[hh[0]];
	for (h = 0; h < m; h++) {
		y = max(y, yy[hh[h]]);
		ans = min(ans, y - (h + 1 < m ? xx[hh[h + 1]] : (double) ss[n] / n));
	}
	printf("%.12f\n", ans);
	return 0;
}

Compilation message

seesaw.c: In function 'main':
seesaw.c:41:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
seesaw.c:44:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 332 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 1 ms 332 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 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 1 ms 332 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 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 1 ms 332 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 94 ms 8460 KB Output is correct
13 Correct 90 ms 8460 KB Output is correct
14 Correct 88 ms 8396 KB Output is correct
15 Correct 97 ms 8380 KB Output is correct
16 Correct 90 ms 8368 KB Output is correct