Submission #1028731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028731		VectorLi	XOR (IZhO12_xor)	C++14	100 / 100	84 ms	48748 KiB

xor

#include <bits/stdc++.h>
#define long long long

using namespace std;

const int N = 250000;

struct trie {
	int n;
	int e[N * 30 + 1][2];
	int m[N * 30 + 1];
	
	trie() {
		for (int i = 0; i < N * 30 + 1; i++) {
			m[i] = numeric_limits<int>::max();
		}
	}
	
	void insert(int x, int p) {
		int u = 0;
		for (int i = 29; i >= 0; i--) {
			m[u] = min(m[u], p);
			int &v = e[u][(x >> i) & 1];
			if (v == 0) {
				v = ++n;
			}
			u = v;
		}
		m[u] = min(m[u], p);
	}
	
	int query(int x, int k) {
		int u = 0;
		int h = numeric_limits<int>::max(); 
		for (int i = 29; i >= 0; i--) {
			int b = (x >> i) & 1;
			if ((k >> i) & 1) {
				if (e[u][b ^ 1] == 0) {
					break;
				} else {
					k = k - (1 << i);
					u = e[u][b ^ 1];
				}
			} else {
				if (e[u][b ^ 1] > 0) {
					h = min(h, m[e[u][b ^ 1]]);
				}
				if (e[u][b] == 0) {
					break;
				} else {
					u = e[u][b];
				}
			}
		}
		return h;
	}
} t;

int main() {
//#ifdef LOCAL
//	freopen("A.out", "w", stdout);
//#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, k;
	cin >> n >> k;
	k = k - 1;
	
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	vector<int> s(n + 1);
	for (int i = 0; i < n; i++) {
		s[i + 1] = s[i] ^ a[i];
	}
	
//	for (int i = 0; i < n + 1; i++) {
//		cout << s[i] << " ";
//	}
//	cout << (32 ^ 65) << "\n";
//	
//	cout << "\n";
	
	t.insert(0, 0);
//	t.insert(32, 1); 
	
//	cout << t.query(65, 82);
	
	int l = 0, st = 0;
	for (int i = 1; i < n + 1; i++) {
		int p = t.query(s[i], k);
		if (p == numeric_limits<int>::max()) {
			t.insert(s[i], i);
			continue;
		}
		if (i - p > l) {
			l = i - p;
			st = p;
		}
		t.insert(s[i], i);
	}
	cout << st + 1 << " " << l << "\n";
	
	return 0;
}

• Subtask 1: 100 / 100