oj.uz

Submission #1049084

# Submission time Handle Problem Language Result Execution time Memory
1049084 2024-08-08T13:13:01 Z rainboy Brought Down the Grading Server? (CEOI23_balance) C
15 / 100
 60 ms 18768 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 1 ms 6492 KB Correct
2 Incorrect 1 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 50 ms 16548 KB Correct
2 Correct 33 ms 17600 KB Correct
3 Correct 49 ms 15976 KB Correct
4 Correct 23 ms 14864 KB Correct
5 Correct 30 ms 16792 KB Correct
6 Correct 60 ms 18512 KB Correct
7 Correct 53 ms 11976 KB Correct
8 Correct 44 ms 18768 KB Correct
9 Correct 31 ms 18720 KB Correct
10 Correct 31 ms 18764 KB Correct
11 Correct 46 ms 18584 KB Correct

Subtask #2-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16548 KB Correct
2 Correct 33 ms 17600 KB Correct
3 Correct 49 ms 15976 KB Correct
4 Correct 23 ms 14864 KB Correct
5 Correct 30 ms 16792 KB Correct
6 Correct 60 ms 18512 KB Correct
7 Correct 53 ms 11976 KB Correct
8 Correct 44 ms 18768 KB Correct
9 Correct 31 ms 18720 KB Correct
10 Correct 31 ms 18764 KB Correct
11 Correct 46 ms 18584 KB Correct
12 Correct 48 ms 17704 KB Correct
13 Correct 33 ms 17576 KB Correct
14 Correct 31 ms 15920 KB Correct
15 Correct 22 ms 15032 KB Correct
16 Correct 29 ms 17044 KB Correct
17 Correct 38 ms 18524 KB Correct
18 Correct 31 ms 12088 KB Correct
19 Correct 31 ms 15452 KB Correct
20 Correct 33 ms 15420 KB Correct
21 Correct 29 ms 15440 KB Correct
22 Correct 46 ms 15448 KB Correct
23 Runtime error 28 ms 18512 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #2-3
0.0 / 5.0

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

Subtask #3-1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 2 ms 860 KB Correct
3 Incorrect 3 ms 856 KB Output for core 3 doesn't match the input tasks
4 Halted 0 ms 0 KB -

Subtask #3-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 2 ms 860 KB Correct
3 Incorrect 3 ms 856 KB Output for core 3 doesn't match the input tasks
4 Halted 0 ms 0 KB -

Subtask #3-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 2 ms 860 KB Correct
3 Incorrect 3 ms 856 KB Output for core 3 doesn't match the input tasks
4 Halted 0 ms 0 KB -

Subtask #4-1
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16548 KB Correct
2 Correct 33 ms 17600 KB Correct
3 Correct 49 ms 15976 KB Correct
4 Correct 23 ms 14864 KB Correct
5 Correct 30 ms 16792 KB Correct
6 Correct 60 ms 18512 KB Correct
7 Correct 53 ms 11976 KB Correct
8 Correct 44 ms 18768 KB Correct
9 Correct 31 ms 18720 KB Correct
10 Correct 31 ms 18764 KB Correct
11 Correct 46 ms 18584 KB Correct
12 Correct 0 ms 348 KB Correct
13 Correct 2 ms 860 KB Correct
14 Incorrect 3 ms 856 KB Output for core 3 doesn't match the input tasks
15 Halted 0 ms 0 KB -

Subtask #4-2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16548 KB Correct
2 Correct 33 ms 17600 KB Correct
3 Correct 49 ms 15976 KB Correct
4 Correct 23 ms 14864 KB Correct
5 Correct 30 ms 16792 KB Correct
6 Correct 60 ms 18512 KB Correct
7 Correct 53 ms 11976 KB Correct
8 Correct 44 ms 18768 KB Correct
9 Correct 31 ms 18720 KB Correct
10 Correct 31 ms 18764 KB Correct
11 Correct 46 ms 18584 KB Correct
12 Correct 48 ms 17704 KB Correct
13 Correct 33 ms 17576 KB Correct
14 Correct 31 ms 15920 KB Correct
15 Correct 22 ms 15032 KB Correct
16 Correct 29 ms 17044 KB Correct
17 Correct 38 ms 18524 KB Correct
18 Correct 31 ms 12088 KB Correct
19 Correct 31 ms 15452 KB Correct
20 Correct 33 ms 15420 KB Correct
21 Correct 29 ms 15440 KB Correct
22 Correct 46 ms 15448 KB Correct
23 Runtime error 28 ms 18512 KB Execution killed with signal 11
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 1 ms 6492 KB Correct
4 Incorrect 1 ms 6492 KB Integer 30 violates the range [1, 20]
5 Halted 0 ms 0 KB -