Submission #854518

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
854518	2023-09-27T19:42:14 Z	OAleksa	XOR (IZhO12_xor)	C++14	100 / 100	105 ms	89168 KB

xor

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
#define int long long
const int maxn = 250069;
int trie[30 * maxn][2], n, a[maxn], id, y;
int c[30 * maxn];
void add(int x, int p) {
	int node = 0;
	for (int i = 29;i >= 0;i--) {
		int k = ((x & (1 << i)) > 0);
		if (trie[node][k] == 0)
			trie[node][k] = ++id;
		node = trie[node][k];
		c[node] = min(c[node], p);
	}
}
int search(int x) {
	int res = n + 1, node = 0;
	for (int i = 29;i >= 0;i--) {
		int k = ((x & (1 << i)) > 0);
		if (y & (1 << i)) {
			if (k > 0) {
				if (trie[node][0] == 0)
					break;
				node = trie[node][0];
			}
			else {
				if (trie[node][1] == 0)
					break;
				node = trie[node][1];
			}
		}
		else {
			if (k > 0) {
				if (trie[node][0] > 0)
					res = min(res, c[trie[node][0]]);
				node = trie[node][1];
			}
			else {
				if (trie[node][1] > 0)
					res = min(res, c[trie[node][1]]);
				node = trie[node][0];
			}
		}
	}
	return res;
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		cin >> n >> y;
		--y;
		// treba mi strknto veci od y sad
		for (int i = 1;i <= n;i++) 
			cin >> a[i];
		for (int i = 1;i < 30 * maxn;i++)
			c[i] = n + 1;
		add(0, 0);
		int ind = 0, k = 0, xr = 0;
		for (int i = 1;i <= n;i++) {
			xr ^= a[i];
			add(xr, i);
			int rez = search(xr);
			if (i - rez > k) {
				k = i - rez;
				ind = rez;
			}
			else if (rez == k) 
				ind = min(ind, rez);
		}
		cout << ind + 1 << " " << k;
	}	
   return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	62044 KB	Output is correct
2	Correct	11 ms	62148 KB	Output is correct
3	Correct	8 ms	62044 KB	Output is correct
4	Correct	9 ms	62196 KB	Output is correct
5	Correct	12 ms	62204 KB	Output is correct
6	Correct	13 ms	62040 KB	Output is correct
7	Correct	13 ms	62044 KB	Output is correct
8	Correct	14 ms	62044 KB	Output is correct
9	Correct	36 ms	74220 KB	Output is correct
10	Correct	35 ms	74320 KB	Output is correct
11	Correct	36 ms	74324 KB	Output is correct
12	Correct	35 ms	74324 KB	Output is correct
13	Correct	44 ms	74364 KB	Output is correct
14	Correct	48 ms	74476 KB	Output is correct
15	Correct	47 ms	74324 KB	Output is correct
16	Correct	35 ms	74324 KB	Output is correct
17	Correct	96 ms	88992 KB	Output is correct
18	Correct	96 ms	89036 KB	Output is correct
19	Correct	105 ms	89168 KB	Output is correct
20	Correct	96 ms	88984 KB	Output is correct