Submission #854518

#	Time	Username	Problem	Language	Result	Execution time	Memory
854518		OAleksa	XOR (IZhO12_xor)	C++14	100 / 100	105 ms	89168 KiB

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