Submission #785008

#	Time	Username	Problem	Language	Result	Execution time	Memory
785008		rainboy	Xor Sort (eJOI20_xorsort)	C11	100 / 100	6 ms	856 KiB

xorsort

#include <stdio.h>

#define N	1000
#define L	20
#define M	40000

int max(int a, int b) { return a > b ? a : b; }

int *aa_, *ii_, *jj_, m;

void move(int i, int j) {
	ii_[m] = i, jj_[m] = j, m++;
	aa_[i] ^= aa_[j];
}

int reduce(int *aa, int *ii, int *jj, int n, int s) {
	int r, i, j, k, l;

	aa_ = aa, ii_ = ii, jj_ = jj, m = 0;
	r = 0;
	for (l = L - 1; l >= 0; l--) {
		for (i = 0; i + 1 < n - r; i++)
			if ((aa[i] & 1 << l) != 0) {
				if ((aa[i + 1] & 1 << l) == 0)
					move(i + 1, i);
				move(i, i + 1);
			}
		if ((aa[n - 1 - r] & 1 << l) != 0)
			r++;
	}
	if (s == 1)
		for (i = n - r; i < n; i++) {
			l = L - 1;
			while ((aa[i] & 1 << l) == 0)
				l--;
			for (j = n - 1; j > i; j--)
				if ((aa[j] & 1 << l) != 0) {
					for (k = j; k > i + 1; k--)
						move(k, k - 1);
					for (k = i + 1; k <= j; k++)
						move(k, k - 1);
				}
		}
	return m;
}

int main() {
	static int aa1[N], aa2[N], ii1[M], jj1[M], ii2[M], jj2[M];
	int n, m1, m2, s, h, i, j, r, b;

	scanf("%d%d", &n, &s);
	for (i = 0; i < n; i++)
		scanf("%d", &aa1[i]);
	m1 = reduce(aa1, ii1, jj1, n, 1);
	if (s == 2)
		m2 = 0;
	else {
		r = 0;
		while (r < n && aa1[n - 1 - r] > 0)
			r++;
		for (i = 0; i < n; i++) {
			b = max(i, i < n - r ? 0 : 1 << i - n + r);
			aa2[i] = 0;
			for (j = 0; j < r; j++)
				if ((b & 1 << j) != 0)
					aa2[i] ^= aa1[n - r + j];
		}
		m2 = reduce(aa2, ii2, jj2, n, 1);
	}
	printf("%d\n", m1 + m2);
	for (h = 0; h < m1; h++)
		printf("%d %d\n", ii1[h] + 1, jj1[h] + 1);
	for (h = m2 - 1; h >= 0; h--)
		printf("%d %d\n", ii2[h] + 1, jj2[h] + 1);
	return 0;
}

Compilation message (stderr)

xorsort.c: In function 'main':
xorsort.c:62:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   62 |    b = max(i, i < n - r ? 0 : 1 << i - n + r);
      |                                    ~~~~~~^~~
xorsort.c:51:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d%d", &n, &s);
      |  ^~~~~~~~~~~~~~~~~~~~~
xorsort.c:53:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d", &aa1[i]);
      |   ^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40