oj.uz

Submission #916326

# Submission time Handle Problem Language Result Execution time Memory
916326 2024-01-25T16:33:10 Z rainboy XOR Sum (info1cup17_xorsum) C
100 / 100
 322 ms 21492 KB 
#include <stdio.h>
#include <string.h>

#define N	1000000
#define L	29	/* L = floor(log2(10^9)) */

int main() {
	static int aa[N], aa0[N], aa1[N];
	int n, n0, n1, i, i0, i1, l, ans, k;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	ans = 0;
	if (n % 2 == 0)
		for (i = 0; i < n; i++)
			ans ^= aa[i];
	for (l = 1; l <= L; l++) {
		n0 = 0, n1 = 0;
		for (i = 0; i < n; i++)
			if ((aa[i] & 1 << l - 1) == 0)
				aa0[n0++] = aa[i];
			else
				aa1[n1++] = aa[i];
		k = (long long) n1 * (n1 + 1) / 2 % 2;
		for (i0 = 0, i1 = n1 - 1; i0 < n0; i0++) {
			while (i1 >= 0 && (aa0[i0] & (1 << l) - 1) + (aa1[i1] & (1 << l) - 1) >= 1 << l)
				i1--;
			if ((n1 - 1 - i1) % 2 != 0)
				k ^= 1;
		}
		memcpy(aa, aa0, n0 * sizeof *aa0), memcpy(aa + n0, aa1, n1 * sizeof *aa1);
		if (k)
			ans ^= 1 << l;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

xorsum.c: In function 'main':
xorsum.c:21:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   21 |    if ((aa[i] & 1 << l - 1) == 0)
      |                      ~~^~~
xorsum.c:27:42: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   27 |    while (i1 >= 0 && (aa0[i0] & (1 << l) - 1) + (aa1[i1] & (1 << l) - 1) >= 1 << l)
      |                                 ~~~~~~~~~^~~
xorsum.c:27:69: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   27 |    while (i1 >= 0 && (aa0[i0] & (1 << l) - 1) + (aa1[i1] & (1 << l) - 1) >= 1 << l)
      |                                                            ~~~~~~~~~^~~
xorsum.c:11:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
xorsum.c:13:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 16724 KB Output is correct
2 Correct 153 ms 16060 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 16724 KB Output is correct
2 Correct 153 ms 16060 KB Output is correct
3 Correct 215 ms 19096 KB Output is correct
4 Correct 212 ms 18464 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 31 ms 5720 KB Output is correct
4 Correct 31 ms 5720 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 167 ms 16724 KB Output is correct
4 Correct 153 ms 16060 KB Output is correct
5 Correct 215 ms 19096 KB Output is correct
6 Correct 212 ms 18464 KB Output is correct
7 Correct 31 ms 5720 KB Output is correct
8 Correct 31 ms 5720 KB Output is correct
9 Correct 287 ms 21492 KB Output is correct
10 Correct 322 ms 21328 KB Output is correct
11 Correct 290 ms 21492 KB Output is correct