Submission #1049088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049088		rainboy	Brought Down the Grading Server? (CEOI23_balance)	C11	50 / 100	161 ms	33012 KiB

balance

#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 (stderr)

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
• Subtask 1: 0 / 10
• Subtask 2-1: 15 / 15
• Subtask 2-2: 0 / 5
• Subtask 2-3: 0 / 5
• Subtask 3-1: 15 / 15
• Subtask 3-2: 0 / 5
• Subtask 3-3: 0 / 5
• Subtask 4-1: 20 / 20
• Subtask 4-2: 0 / 10
• Subtask 4-3: 0 / 10