Submission #1259387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259387		proofy	XOR (IZhO12_xor)	C++20	0 / 100	0 ms	324 KiB

xor

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int B = 30;
const int N = 250123;

int trie[N * B][2], id;
int max_index[N * B], lower;

void insert(int x, int index, int i = B - 1, int v = 0) {
	if (i == -1) return void(max_index[v] = index);
	int b = (x >> i) & 1;

	if (!trie[v][b]) trie[v][b] = ++id;
	int u = trie[v][b];

	insert(x, index, i - 1, u);
	
	max_index[v] = max(max_index[v], max_index[u]);
}

int query(int x) {
	int number_so_far = 0, v = 0, res = -1;
	for (int i = B - 1; i >= 0; --i) {
		int b = (x >> i) & 1;
		int b2 = (lower >> i) & 1;

		if (b2) {
			if (!trie[v][1 - b]) return res;
			number_so_far ^= (1 << i);
			v = trie[v][1 - b];
		} else {
			if (trie[v][1 - b]) {
				res = max(res, max_index[trie[v][1 - b]]);
				if (!trie[v][b]) return res;
			}
			assert(trie[v][b]);
			v = trie[v][b];
		}
	}
	assert(number_so_far == lower);
	return max(res, max_index[v]);
}

int p[N], n;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> lower;
	for (int i = 1; i <= n; i++) cin >> p[i];
	for (int i = n; i >= 1; --i) p[i] ^= p[i + 1];

	insert(0, n + 1);
	int best = -1, max_interval = 0;
	for (int i = n; i >= 1; --i) {
		int k = query(p[i]) - i;
		if (k >= max_interval) {
			max_interval = k;
			best = i;
		}
		insert(p[i], i);
	}

	cout << best << " " << max_interval << "\n";
}

• Subtask 1: 0 / 100