oj.uz

Submission #768792

# Submission time Handle Problem Language Result Execution time Memory
768792 2023-06-28T15:42:29 Z rainboy Gift (IZhO18_nicegift) C
100 / 100
 495 ms 64644 KB 
#include <stdio.h>

#define N	1000000
#define L	3000000

long long min(long long a, long long b) { return a < b ? a : b; }

unsigned int X = 12345;

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

long long aa[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 (aa[ii[j]] == aa[i_])
				j++;
			else if (aa[ii[j]] < aa[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], iii[L];
	static long long xx[N + 1];
	int n, m, k, g, h, i, j;
	long long sum, cnt, x;

	scanf("%d%d", &n, &k);
	sum = 0;
	for (i = 0; i < n; i++) {
		scanf("%lld", &aa[i]);
		sum += aa[i];
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	if (sum % k != 0) {
		printf("-1\n");
		return 0;
	}
	cnt = sum / k;
	if (aa[ii[n - 1]] > cnt) {
		printf("-1\n");
		return 0;
	}
	m = 0, i = 0, j = n - 1;
	while (cnt > 0) {
		while (i < n - k && aa[ii[i]] == 0)
			i++;
		while (j >= n - k && aa[ii[j]] == cnt)
			j--;
		if (i == n - k)
			x = aa[ii[n - k]];
		else
			x = min(aa[ii[i]], cnt - aa[ii[j]]);
		xx[m] = x;
		for (h = i; h < i + k - (n - 1 - j); h++)
			aa[iii[m * k + h - i] = ii[h]] -= x;
		for (h = j + 1; h < n; h++)
			aa[iii[m * k + k - n + h] = ii[h]] -= x;
		cnt -= x;
		m++;
	}
	printf("%d\n", m);
	for (g = 0; g < m; g++) {
		printf("%lld", xx[g]);
		for (h = 0; h < k; h++)
			printf(" %d", iii[g * k + h] + 1);
		printf("\n");
	}
	return 0;
}

Compilation message

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n=4
2 Correct 1 ms 300 KB n=3
3 Correct 0 ms 212 KB n=3
4 Correct 0 ms 212 KB n=4
5 Correct 0 ms 212 KB n=4
6 Correct 1 ms 212 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n=4
2 Correct 1 ms 300 KB n=3
3 Correct 0 ms 212 KB n=3
4 Correct 0 ms 212 KB n=4
5 Correct 0 ms 212 KB n=4
6 Correct 1 ms 212 KB n=2
7 Correct 0 ms 212 KB n=5
8 Correct 1 ms 296 KB n=8
9 Correct 0 ms 212 KB n=14
10 Correct 0 ms 296 KB n=11
11 Correct 9 ms 1868 KB n=50000
12 Correct 10 ms 1620 KB n=50000
13 Correct 0 ms 212 KB n=10
14 Correct 1 ms 340 KB n=685
15 Correct 1 ms 340 KB n=623
16 Correct 1 ms 340 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n=4
2 Correct 1 ms 300 KB n=3
3 Correct 0 ms 212 KB n=3
4 Correct 0 ms 212 KB n=4
5 Correct 0 ms 212 KB n=4
6 Correct 1 ms 212 KB n=2
7 Correct 0 ms 212 KB n=5
8 Correct 1 ms 296 KB n=8
9 Correct 0 ms 212 KB n=14
10 Correct 0 ms 296 KB n=11
11 Correct 9 ms 1868 KB n=50000
12 Correct 10 ms 1620 KB n=50000
13 Correct 0 ms 212 KB n=10
14 Correct 1 ms 340 KB n=685
15 Correct 1 ms 340 KB n=623
16 Correct 1 ms 340 KB n=973
17 Correct 1 ms 340 KB n=989
18 Correct 1 ms 340 KB n=563
19 Correct 1 ms 340 KB n=592
20 Correct 1 ms 340 KB n=938
21 Correct 1 ms 340 KB n=747
22 Correct 1 ms 340 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 47536 KB n=1000000
2 Correct 135 ms 29336 KB n=666666
3 Correct 75 ms 16368 KB n=400000
4 Correct 53 ms 11468 KB n=285714
5 Correct 4 ms 980 KB n=20000
6 Correct 35 ms 7116 KB n=181818
7 Correct 2 ms 664 KB n=10000
8 Correct 2 ms 468 KB n=6666
9 Correct 1 ms 340 KB n=4000
10 Correct 2 ms 468 KB n=2857
11 Correct 1 ms 328 KB n=2000

Subtask #5
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n=4
2 Correct 1 ms 300 KB n=3
3 Correct 0 ms 212 KB n=3
4 Correct 0 ms 212 KB n=4
5 Correct 0 ms 212 KB n=4
6 Correct 1 ms 212 KB n=2
7 Correct 0 ms 212 KB n=5
8 Correct 1 ms 296 KB n=8
9 Correct 0 ms 212 KB n=14
10 Correct 0 ms 296 KB n=11
11 Correct 9 ms 1868 KB n=50000
12 Correct 10 ms 1620 KB n=50000
13 Correct 0 ms 212 KB n=10
14 Correct 1 ms 340 KB n=685
15 Correct 1 ms 340 KB n=623
16 Correct 1 ms 340 KB n=973
17 Correct 1 ms 340 KB n=989
18 Correct 1 ms 340 KB n=563
19 Correct 1 ms 340 KB n=592
20 Correct 1 ms 340 KB n=938
21 Correct 1 ms 340 KB n=747
22 Correct 1 ms 340 KB n=991
23 Correct 214 ms 47536 KB n=1000000
24 Correct 135 ms 29336 KB n=666666
25 Correct 75 ms 16368 KB n=400000
26 Correct 53 ms 11468 KB n=285714
27 Correct 4 ms 980 KB n=20000
28 Correct 35 ms 7116 KB n=181818
29 Correct 2 ms 664 KB n=10000
30 Correct 2 ms 468 KB n=6666
31 Correct 1 ms 340 KB n=4000
32 Correct 2 ms 468 KB n=2857
33 Correct 1 ms 328 KB n=2000
34 Correct 10 ms 1364 KB n=23514
35 Correct 9 ms 1468 KB n=23514
36 Correct 1 ms 340 KB n=940
37 Correct 1 ms 212 KB n=2
38 Correct 50 ms 7756 KB n=100000
39 Correct 50 ms 7756 KB n=100000
40 Correct 0 ms 212 KB n=10
41 Correct 1 ms 340 KB n=100
42 Correct 4 ms 724 KB n=1000
43 Correct 338 ms 55080 KB n=1000000
44 Correct 495 ms 64644 KB n=1000000
45 Correct 393 ms 50080 KB n=666666
46 Correct 271 ms 37872 KB n=400000
47 Correct 135 ms 17220 KB n=2336
48 Correct 236 ms 32836 KB n=285714
49 Correct 197 ms 28212 KB n=181818
50 Correct 141 ms 21124 KB n=40000
51 Correct 141 ms 19760 KB n=20000
52 Correct 129 ms 18224 KB n=10000
53 Correct 135 ms 18084 KB n=6666
54 Correct 141 ms 17484 KB n=4000
55 Correct 135 ms 17388 KB n=2857
56 Correct 67 ms 8732 KB n=2000