oj.uz

Submission #1049088

# Submission time Handle Problem Language Result Execution time Memory
1049088 2024-08-08T13:16:39 Z rainboy Brought Down the Grading Server? (CEOI23_balance) C
50 / 100
 161 ms 33012 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	100000
#define M	500000

int ij[M]; char used[M];
int *eh[N], eo[N], n, m, k;
int ii_[N], n_;

void append(int i, int h) {
	int o = eo[i]++;

	if (o == 0) {
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
		ii_[n_++] = i;
	} else if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

int hh[M], cnt;

void dfs(int i) {
	while (eo[i]) {
		int h = eh[i][--eo[i]], j = i ^ ij[h];

		if (!used[h])
			used[h] = 1, dfs(j), hh[cnt++] = h;
	}
}

void solve(int *ii, int m) {
	static char odd[N];
	int g, h, h_, i, i_, j;

	if (m == 1)
		return;
	m /= 2;
	n_ = 0;
	for (h = 0; h < m; h++)
		for (g = 0; g < k; g++) {
			h_ = h * k + g, i = ii[h_], j = ii[m * k + h_];
			ij[h_] = i ^ j, used[h_] = 0;
			append(i, h_), append(j, h_);
		}
	for (i = 0; i < n_; i++) {
		i_ = ii_[i];
		if (eo[i_] % 2 != 0)
			odd[i_] = 1;
	}
	for (i = 0; i < n_; i++) {
		i_ = ii_[i];
		if (odd[i_]) {
			cnt = 0, dfs(i_);
			while (cnt--) {
				h_ = hh[cnt], h = h_ / k, g = h_ % k;
				ii[h_] = i_, ii[m * k + h_] = i_ ^= ij[h_];
			}
		}
	}
	for (i = 0; i < n_; i++) {
		i_ = ii_[i];
		cnt = 0, dfs(i_);
		while (cnt--) {
			h_ = hh[cnt], h = h_ / k, g = h_ % k;
			ii[h_] = i_, ii[m * k + h_] = i_ ^= ij[h_];
		}
	}
	for (i = 0; i < n_; i++) {
		i_ = ii_[i];
		free(eh[i_]), eh[i_] = NULL, eo[i_] = 0;
		odd[i_] = 0;
	}
	solve(ii, m), solve(ii + m * k, m);
}

int main() {
	static int ii[M];
	int g, h;

	scanf("%d%d%d", &k, &m, &n);
	for (g = 0; g < k; g++)
		for (h = 0; h < m; h++)
			scanf("%d", &ii[h * k + g]), ii[h * k + g]--;
	solve(ii, m);
	for (g = 0; g < k; g++) {
		for (h = 0; h < m; h++)
			printf("%d ", ii[h * k + g] + 1);
		printf("\n");
	}
	return 0;
}

Compilation message

balance.c: In function 'append':
balance.c:17:30: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   17 |  } else if (o >= 2 && (o & o - 1) == 0)
      |                            ~~^~~
balance.c: In function 'main':
balance.c:82:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  scanf("%d%d%d", &k, &m, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
balance.c:85:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |    scanf("%d", &ii[h * k + g]), ii[h * k + g]--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Correct
2 Correct 1 ms 6492 KB Correct

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6488 KB Correct
2 Incorrect 0 ms 6492 KB Integer 30 violates the range [1, 20]
3 Halted 0 ms 0 KB -

Subtask #2-1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 17236 KB Correct
2 Correct 32 ms 17328 KB Correct
3 Correct 33 ms 15712 KB Correct
4 Correct 22 ms 14680 KB Correct
5 Correct 30 ms 16584 KB Correct
6 Correct 35 ms 18004 KB Correct
7 Correct 30 ms 11600 KB Correct
8 Correct 33 ms 18260 KB Correct
9 Correct 30 ms 18256 KB Correct
10 Correct 27 ms 18256 KB Correct
11 Correct 28 ms 18256 KB Correct

Subtask #2-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 17236 KB Correct
2 Correct 32 ms 17328 KB Correct
3 Correct 33 ms 15712 KB Correct
4 Correct 22 ms 14680 KB Correct
5 Correct 30 ms 16584 KB Correct
6 Correct 35 ms 18004 KB Correct
7 Correct 30 ms 11600 KB Correct
8 Correct 33 ms 18260 KB Correct
9 Correct 30 ms 18256 KB Correct
10 Correct 27 ms 18256 KB Correct
11 Correct 28 ms 18256 KB Correct
12 Correct 37 ms 17232 KB Correct
13 Correct 32 ms 17328 KB Correct
14 Correct 31 ms 15700 KB Correct
15 Correct 22 ms 14940 KB Correct
16 Correct 36 ms 16588 KB Correct
17 Correct 34 ms 17964 KB Correct
18 Correct 30 ms 11600 KB Correct
19 Correct 31 ms 18256 KB Correct
20 Correct 30 ms 18260 KB Correct
21 Correct 29 ms 18260 KB Correct
22 Correct 27 ms 18260 KB Correct
23 Incorrect 35 ms 14164 KB Integer 109951 violates the range [1, 100000]
24 Halted 0 ms 0 KB -

Subtask #2-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6488 KB Correct
2 Incorrect 0 ms 6492 KB Integer 30 violates the range [1, 20]
3 Halted 0 ms 0 KB -

Subtask #3-1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Correct
2 Correct 3 ms 6840 KB Correct
3 Correct 4 ms 6748 KB Correct
4 Correct 2 ms 7004 KB Correct
5 Correct 2 ms 7004 KB Correct
6 Correct 2 ms 7000 KB Correct
7 Correct 2 ms 6880 KB Correct
8 Correct 2 ms 7004 KB Correct
9 Correct 3 ms 6728 KB Correct
10 Correct 2 ms 7004 KB Correct
11 Correct 2 ms 6748 KB Correct
12 Correct 2 ms 7004 KB Correct
13 Correct 2 ms 7004 KB Correct
14 Correct 2 ms 7004 KB Correct

Subtask #3-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Correct
2 Correct 3 ms 6840 KB Correct
3 Correct 4 ms 6748 KB Correct
4 Correct 2 ms 7004 KB Correct
5 Correct 2 ms 7004 KB Correct
6 Correct 2 ms 7000 KB Correct
7 Correct 2 ms 6880 KB Correct
8 Correct 2 ms 7004 KB Correct
9 Correct 3 ms 6728 KB Correct
10 Correct 2 ms 7004 KB Correct
11 Correct 2 ms 6748 KB Correct
12 Correct 2 ms 7004 KB Correct
13 Correct 2 ms 7004 KB Correct
14 Correct 2 ms 7004 KB Correct
15 Correct 1 ms 6492 KB Correct
16 Correct 3 ms 7004 KB Correct
17 Correct 3 ms 6748 KB Correct
18 Correct 2 ms 6888 KB Correct
19 Correct 2 ms 7004 KB Correct
20 Correct 2 ms 7004 KB Correct
21 Correct 2 ms 7032 KB Correct
22 Correct 2 ms 7004 KB Correct
23 Correct 2 ms 6748 KB Correct
24 Correct 2 ms 7004 KB Correct
25 Correct 2 ms 6748 KB Correct
26 Correct 2 ms 7004 KB Correct
27 Correct 2 ms 7004 KB Correct
28 Correct 2 ms 7004 KB Correct
29 Incorrect 3 ms 7004 KB Integer 60 violates the range [1, 50]
30 Halted 0 ms 0 KB -

Subtask #3-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Correct
2 Correct 3 ms 6840 KB Correct
3 Correct 4 ms 6748 KB Correct
4 Correct 2 ms 7004 KB Correct
5 Correct 2 ms 7004 KB Correct
6 Correct 2 ms 7000 KB Correct
7 Correct 2 ms 6880 KB Correct
8 Correct 2 ms 7004 KB Correct
9 Correct 3 ms 6728 KB Correct
10 Correct 2 ms 7004 KB Correct
11 Correct 2 ms 6748 KB Correct
12 Correct 2 ms 7004 KB Correct
13 Correct 2 ms 7004 KB Correct
14 Correct 2 ms 7004 KB Correct
15 Correct 1 ms 6492 KB Correct
16 Correct 3 ms 7004 KB Correct
17 Correct 3 ms 6748 KB Correct
18 Correct 2 ms 6888 KB Correct
19 Correct 2 ms 7004 KB Correct
20 Correct 2 ms 7004 KB Correct
21 Correct 2 ms 7032 KB Correct
22 Correct 2 ms 7004 KB Correct
23 Correct 2 ms 6748 KB Correct
24 Correct 2 ms 7004 KB Correct
25 Correct 2 ms 6748 KB Correct
26 Correct 2 ms 7004 KB Correct
27 Correct 2 ms 7004 KB Correct
28 Correct 2 ms 7004 KB Correct
29 Incorrect 3 ms 7004 KB Integer 60 violates the range [1, 50]
30 Halted 0 ms 0 KB -

Subtask #4-1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 17236 KB Correct
2 Correct 32 ms 17328 KB Correct
3 Correct 33 ms 15712 KB Correct
4 Correct 22 ms 14680 KB Correct
5 Correct 30 ms 16584 KB Correct
6 Correct 35 ms 18004 KB Correct
7 Correct 30 ms 11600 KB Correct
8 Correct 33 ms 18260 KB Correct
9 Correct 30 ms 18256 KB Correct
10 Correct 27 ms 18256 KB Correct
11 Correct 28 ms 18256 KB Correct
12 Correct 1 ms 6492 KB Correct
13 Correct 3 ms 6840 KB Correct
14 Correct 4 ms 6748 KB Correct
15 Correct 2 ms 7004 KB Correct
16 Correct 2 ms 7004 KB Correct
17 Correct 2 ms 7000 KB Correct
18 Correct 2 ms 6880 KB Correct
19 Correct 2 ms 7004 KB Correct
20 Correct 3 ms 6728 KB Correct
21 Correct 2 ms 7004 KB Correct
22 Correct 2 ms 6748 KB Correct
23 Correct 2 ms 7004 KB Correct
24 Correct 2 ms 7004 KB Correct
25 Correct 2 ms 7004 KB Correct
26 Correct 35 ms 17668 KB Correct
27 Correct 34 ms 17572 KB Correct
28 Correct 36 ms 16000 KB Correct
29 Correct 22 ms 14680 KB Correct
30 Correct 30 ms 16996 KB Correct
31 Correct 35 ms 18512 KB Correct
32 Correct 31 ms 12116 KB Correct
33 Correct 35 ms 19024 KB Correct
34 Correct 31 ms 18608 KB Correct
35 Correct 27 ms 18776 KB Correct
36 Correct 27 ms 18768 KB Correct
37 Correct 1 ms 6488 KB Correct
38 Correct 3 ms 7004 KB Correct
39 Correct 3 ms 6748 KB Correct
40 Correct 2 ms 7004 KB Correct
41 Correct 2 ms 7004 KB Correct
42 Correct 2 ms 7004 KB Correct
43 Correct 2 ms 7004 KB Correct
44 Correct 3 ms 6840 KB Correct
45 Correct 2 ms 6748 KB Correct
46 Correct 2 ms 7004 KB Correct
47 Correct 2 ms 6748 KB Correct
48 Correct 2 ms 7004 KB Correct
49 Correct 2 ms 7004 KB Correct
50 Correct 2 ms 7004 KB Correct
51 Correct 137 ms 32492 KB Correct
52 Correct 137 ms 27984 KB Correct
53 Correct 28 ms 10448 KB Correct
54 Correct 44 ms 15500 KB Correct
55 Correct 133 ms 25724 KB Correct
56 Correct 119 ms 31376 KB Correct
57 Correct 133 ms 33012 KB Correct
58 Correct 161 ms 27272 KB Correct
59 Correct 119 ms 23388 KB Correct
60 Correct 115 ms 29520 KB Correct
61 Correct 126 ms 31512 KB Correct
62 Correct 55 ms 21588 KB Correct
63 Correct 54 ms 21776 KB Correct
64 Correct 59 ms 27988 KB Correct
65 Correct 62 ms 27928 KB Correct
66 Correct 68 ms 21844 KB Correct
67 Correct 55 ms 21588 KB Correct
68 Correct 60 ms 27996 KB Correct
69 Correct 68 ms 27988 KB Correct
70 Correct 99 ms 21588 KB Correct
71 Correct 77 ms 23620 KB Correct

Subtask #4-2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 17236 KB Correct
2 Correct 32 ms 17328 KB Correct
3 Correct 33 ms 15712 KB Correct
4 Correct 22 ms 14680 KB Correct
5 Correct 30 ms 16584 KB Correct
6 Correct 35 ms 18004 KB Correct
7 Correct 30 ms 11600 KB Correct
8 Correct 33 ms 18260 KB Correct
9 Correct 30 ms 18256 KB Correct
10 Correct 27 ms 18256 KB Correct
11 Correct 28 ms 18256 KB Correct
12 Correct 37 ms 17232 KB Correct
13 Correct 32 ms 17328 KB Correct
14 Correct 31 ms 15700 KB Correct
15 Correct 22 ms 14940 KB Correct
16 Correct 36 ms 16588 KB Correct
17 Correct 34 ms 17964 KB Correct
18 Correct 30 ms 11600 KB Correct
19 Correct 31 ms 18256 KB Correct
20 Correct 30 ms 18260 KB Correct
21 Correct 29 ms 18260 KB Correct
22 Correct 27 ms 18260 KB Correct
23 Incorrect 35 ms 14164 KB Integer 109951 violates the range [1, 100000]
24 Halted 0 ms 0 KB -

Subtask #4-3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Correct
2 Correct 1 ms 6492 KB Correct
3 Correct 0 ms 6488 KB Correct
4 Incorrect 0 ms 6492 KB Integer 30 violates the range [1, 20]
5 Halted 0 ms 0 KB -