oj.uz

Submission #1049082

# Submission time Handle Problem Language Result Execution time Memory
1049082 2024-08-08T13:12:26 Z rainboy Brought Down the Grading Server? (CEOI23_balance) C
0 / 100
 35 ms 31984 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_]), 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 Runtime error 6 ms 12972 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2-1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 31984 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 31984 KB Execution killed with signal 6
2 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 Runtime error 6 ms 12972 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3-1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6572 KB Correct
2 Runtime error 5 ms 13660 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6572 KB Correct
2 Runtime error 5 ms 13660 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6572 KB Correct
2 Runtime error 5 ms 13660 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4-1
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 31984 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4-2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 31984 KB Execution killed with signal 6
2 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 Runtime error 6 ms 12972 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -