oj.uz

Submission #785008

# Submission time Handle Problem Language Result Execution time Memory
785008 2023-07-16T22:32:18 Z rainboy Xor Sort (eJOI20_xorsort) C
100 / 100
 6 ms 856 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 400 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 400 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 420 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 408 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 4 ms 856 KB Output is correct
8 Correct 4 ms 676 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 6 ms 736 KB Output is correct
13 Correct 4 ms 724 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 5 ms 852 KB Output is correct