Submission #854516

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
854516	2023-09-27T19:38:07 Z	OAleksa	XOR (IZhO12_xor)	C++14	100 / 100	112 ms	91376 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)) {
			int dr;
			if (k > 0)
				dr = 0;
			else
				dr = 1;
			if (!trie[node][dr])
				break;
			node = trie[node][dr];
		}
		else {
			int dr;
			if (k > 0)
				dr = 0;
			else
				dr = 1;
			if (trie[node][dr])
				res = min(res, c[trie[node][dr]]);
			node = trie[node][dr ^ 1];
		}
	}
	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	10 ms	62040 KB	Output is correct
2	Correct	8 ms	62044 KB	Output is correct
3	Correct	9 ms	62152 KB	Output is correct
4	Correct	10 ms	62044 KB	Output is correct
5	Correct	12 ms	62296 KB	Output is correct
6	Correct	14 ms	62300 KB	Output is correct
7	Correct	13 ms	62300 KB	Output is correct
8	Correct	15 ms	62300 KB	Output is correct
9	Correct	35 ms	75092 KB	Output is correct
10	Correct	35 ms	75096 KB	Output is correct
11	Correct	38 ms	74992 KB	Output is correct
12	Correct	37 ms	75092 KB	Output is correct
13	Correct	38 ms	74924 KB	Output is correct
14	Correct	36 ms	75068 KB	Output is correct
15	Correct	35 ms	75212 KB	Output is correct
16	Correct	39 ms	75088 KB	Output is correct
17	Correct	106 ms	91056 KB	Output is correct
18	Correct	97 ms	91148 KB	Output is correct
19	Correct	112 ms	91376 KB	Output is correct
20	Correct	104 ms	90904 KB	Output is correct