Submission #508588

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
508588	2022-01-13T12:38:01 Z	sidon	XOR (IZhO12_xor)	C++17	100 / 100	277 ms	42464 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() {
	ios::sync_with_stdio(0), cin.tie(0);
 
	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;
	}
	if(!X) ind = 1, k = N;
 
	cout << ind << ' ' << k;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	9 ms	1376 KB	Output is correct
6	Correct	11 ms	1484 KB	Output is correct
7	Correct	13 ms	1484 KB	Output is correct
8	Correct	14 ms	1472 KB	Output is correct
9	Correct	97 ms	20092 KB	Output is correct
10	Correct	93 ms	20236 KB	Output is correct
11	Correct	87 ms	20132 KB	Output is correct
12	Correct	85 ms	20072 KB	Output is correct
13	Correct	81 ms	20208 KB	Output is correct
14	Correct	96 ms	20196 KB	Output is correct
15	Correct	88 ms	20120 KB	Output is correct
16	Correct	91 ms	20168 KB	Output is correct
17	Correct	251 ms	42308 KB	Output is correct
18	Correct	262 ms	42380 KB	Output is correct
19	Correct	277 ms	42464 KB	Output is correct
20	Correct	233 ms	42332 KB	Output is correct