Submission #508590

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
508590	2022-01-13T12:39:07 Z	sidon	XOR (IZhO12_xor)	C++17	100 / 100	326 ms	42512 KB

xor

#include <bits/stdc++.h>
using namespace std;
 
int N, X, pref, ind, k, curr, u, j;
int C[2][1<<22], t[1<<22];
 
#define minim(l, r) if(l && r-l > k) k = r-l, ind = l
 
void go(bool c) {
	u = C[c][u] ? : C[c][u] = ++curr;
}
 
int main() {
 	cin >> N >> X;
 
	for(int i = 1; i <= N + 1; i++) {
		for(u = 0, j = 1<<30; j/=2; ) {
			if(!(X & j))
				minim(t[C[!(pref & j)][u]], i);
			go((pref & j) ^ (X & j));
		}
		minim(t[u], i);

		for(u = 0, j = 1<<30; j/=2; ) {
			go(pref & j);
			t[u] = t[u] ? : i;
		} 
		cin >> u;
		pref ^= u;
	}
 	cout << ind << ' ' << k;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	12 ms	1296 KB	Output is correct
6	Correct	17 ms	1476 KB	Output is correct
7	Correct	20 ms	1448 KB	Output is correct
8	Correct	19 ms	1440 KB	Output is correct
9	Correct	104 ms	20028 KB	Output is correct
10	Correct	106 ms	20164 KB	Output is correct
11	Correct	121 ms	20128 KB	Output is correct
12	Correct	110 ms	20144 KB	Output is correct
13	Correct	118 ms	20284 KB	Output is correct
14	Correct	125 ms	20164 KB	Output is correct
15	Correct	96 ms	20140 KB	Output is correct
16	Correct	104 ms	20160 KB	Output is correct
17	Correct	314 ms	42480 KB	Output is correct
18	Correct	326 ms	42384 KB	Output is correct
19	Correct	276 ms	42436 KB	Output is correct
20	Correct	284 ms	42512 KB	Output is correct