Submission #1028678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028678		VectorLi	XOR (IZhO12_xor)	C++14	0 / 100	1 ms	1372 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];
	
	trie() {
		for (int i = 0; i < N; 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) {
					return -1;
				} else {
					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.in", "r", stdin);
#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];
	}
	t.insert(0, 0);
	
	int l = 0, st;
	for (int i = 1; i < n + 1; i++) {
		int p = t.query(s[i], k);
		if (p < 0) {
			continue;
		}
		if (i - p + 1 > l) {
			l = i - p + 1;
			st = i;
		}
		if (i - p + 1 == l && i < st) {
			st = i;
		}
		t.insert(s[i], i);
	}
	cout << st << " " << l << "\n";
	
	return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:95:16: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |  cout << st << " " << l << "\n";
      |                ^~~

• Subtask 1: 0 / 100