Submission #730869

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
730869	2023-04-26T14:41:20 Z	rainboy	XOR (IZhO12_xor)	C	100 / 100	125 ms	24272 KB

xor

#include <stdio.h>

#define N	250000
#define L	30	/* L = ceil(log2(10^9)) */
#define N_	(N * L + 2)

int min(int a, int b) { return a < b ? a : b; }

int tt[N_][2], ii[N_], _ = 2;

int main() {
	static int aa[N + 1];
	int n, x, i, j, i_, j_, l, a, c, t, u;

	scanf("%d%d", &n, &x);
	for (i = 1; i <= n; i++)
		scanf("%d", &aa[i]), aa[i] ^= aa[i - 1];
	i_ = j_ = -1;
	for (j = 0; j <= n; j++) {
		i = j;
		a = aa[j];
		for (l = L - 1, t = 1; l >= 0; l--) {
			c = a >> l & 1;
			if ((x & 1 << l) == 0) {
				if ((u = tt[t][c ^ 1]))
					i = min(i, ii[u]);
				t = tt[t][c];
			} else
				t = tt[t][c ^ 1];
		}
		if (t)
			i = min(i, ii[t]);
		for (l = L - 1, t = 1; l >= 0; l--) {
			c = a >> l & 1;
			if (!tt[t][c])
				ii[tt[t][c] = _++] = j;
			t = tt[t][c];
		}
		if (i < j && j_ - i_ < j - i)
			i_ = i, j_ = j;
	}
	printf("%d %d\n", i_ + 1, j_ - i_);
	return 0;
}

Compilation message

xor.c: In function 'main':
xor.c:15:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d%d", &n, &x);
      |  ^~~~~~~~~~~~~~~~~~~~~
xor.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d", &aa[i]), aa[i] ^= aa[i - 1];
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	308 KB	Output is correct
5	Correct	9 ms	996 KB	Output is correct
6	Correct	9 ms	1072 KB	Output is correct
7	Correct	10 ms	1052 KB	Output is correct
8	Correct	11 ms	1108 KB	Output is correct
9	Correct	40 ms	11328 KB	Output is correct
10	Correct	40 ms	11420 KB	Output is correct
11	Correct	42 ms	11340 KB	Output is correct
12	Correct	41 ms	11312 KB	Output is correct
13	Correct	58 ms	11340 KB	Output is correct
14	Correct	46 ms	11424 KB	Output is correct
15	Correct	46 ms	11340 KB	Output is correct
16	Correct	40 ms	11340 KB	Output is correct
17	Correct	110 ms	24236 KB	Output is correct
18	Correct	118 ms	24232 KB	Output is correct
19	Correct	122 ms	24272 KB	Output is correct
20	Correct	125 ms	24136 KB	Output is correct