Submission #930927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
930927	2024-02-20T20:13:46 Z	rainboy	컬러볼 (KOI15_ball)	C	25 / 25	74 ms	8232 KB

ball

#include <stdio.h>

#define N	200000

unsigned int X = 12345;

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

int cc[N], ww[N];

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

		while (j < k)
			if (ww[ii[j]] == ww[i_])
				j++;
			else if (ww[ii[j]] < ww[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int main() {
	static int ii[N], ss[N], ans[N];
	int n, h, i, i_, j, sum;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &cc[i], &ww[i]), cc[i]--;
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	sum = 0;
	for (i = 0; i < n; i = j) {
		j = i + 1;
		while (j < n && ww[ii[j]] == ww[ii[i]])
			j++;
		for (h = i; h < j; h++) {
			i_ = ii[h];
			ans[i_] = sum - ss[cc[i_]];
		}
		for (h = i; h < j; h++) {
			i_ = ii[h];
			sum += ww[i_], ss[cc[i_]] += ww[i_];
		}
	}
	for (i = 0; i < n; i++)
		printf("%d\n", ans[i]);
	return 0;
}

Compilation message

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

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	8020 KB	Output is correct
2	Correct	64 ms	8232 KB	Output is correct
3	Correct	58 ms	8228 KB	Output is correct
4	Correct	56 ms	8004 KB	Output is correct
5	Correct	74 ms	8016 KB	Output is correct
6	Correct	3 ms	2392 KB	Output is correct
7	Correct	2 ms	2540 KB	Output is correct
8	Correct	2 ms	2396 KB	Output is correct
9	Correct	2 ms	2496 KB	Output is correct
10	Correct	2 ms	2648 KB	Output is correct
11	Correct	53 ms	7364 KB	Output is correct
12	Correct	54 ms	7388 KB	Output is correct
13	Correct	58 ms	7384 KB	Output is correct
14	Correct	53 ms	7504 KB	Output is correct
15	Correct	57 ms	7612 KB	Output is correct
16	Correct	51 ms	7604 KB	Output is correct
17	Correct	51 ms	7668 KB	Output is correct
18	Correct	55 ms	7792 KB	Output is correct
19	Correct	56 ms	8016 KB	Output is correct
20	Correct	56 ms	8020 KB	Output is correct