Submission #1049112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049112		rainboy	Brought Down the Grading Server? (CEOI23_balance)	C11	100 / 100	211 ms	36516 KiB

balance

#include <stdio.h>
#include <stdlib.h>

#define N	100000
#define M	500000
#define M_	(M + N / 2)

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) {
	int g, h, h_, i, i_, j, 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_ = -1, j = 0, h_ = m * k; j < n_; j++) {
		j_ = ii_[j];
		if (eo[j_] % 2 != 0) {
			if (i_ == -1)
				i_ = j_;
			else {
				ij[h_] = i_ ^ j_, used[h_] = 0, append(i_, h_), append(j_, h_), h_++;
				i_ = -1;
			}
		}
	}
	for (i = 0; i < n_; i++) {
		i_ = ii_[i];
		cnt = 0, dfs(i_);
		while (cnt--) {
			h_ = hh[cnt], j_ = i_ ^ ij[h_];
			if (h_ < m * k) {
				h = h_ / k, g = h_ % k;
				ii[h_] = i_, ii[m * k + h_] = j_;
			}
			i_ = j_;
		}
	}
	for (i = 0; i < n_; i++) {
		i_ = ii_[i];
		free(eh[i_]), eh[i_] = NULL, eo[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:18:30: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |  } else if (o >= 2 && (o & o - 1) == 0)
      |                            ~~^~~
balance.c: In function 'main':
balance.c:80:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%d%d", &k, &m, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
balance.c:83:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |    scanf("%d", &ii[h * k + g]), ii[h * k + g]--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2-1: 15 / 15
• Subtask 2-2: 5 / 5
• Subtask 2-3: 5 / 5
• Subtask 3-1: 15 / 15
• Subtask 3-2: 5 / 5
• Subtask 3-3: 5 / 5
• Subtask 4-1: 20 / 20
• Subtask 4-2: 10 / 10
• Subtask 4-3: 10 / 10