Submission #730869

#	Time	Username	Problem	Language	Result	Execution time	Memory
730869		rainboy	XOR (IZhO12_xor)	C11	100 / 100	125 ms	24272 KiB

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

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 / 100