Submission #916326

#	Time	Username	Problem	Language	Result	Execution time	Memory
916326		rainboy	XOR Sum (info1cup17_xorsum)	C11	100 / 100	322 ms	21492 KiB

xorsum

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

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23