Submission #1224760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224760		stdfloat	XOR (IZhO12_xor)	C++20	0 / 100	1 ms	836 KiB

xor

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

using ll = long long;

const int lg = 30;

int id;

vector<int> mn;

vector<vector<int>> ch;

void add(int vl, int ind) {
	// cout << "\nadd " << vl << ' ' << ind << endl;

	int cur = 0;
	for (int i = lg - 1; i >= 0; i--) {
		bool bit = vl >> i & 1;
		if (!~ch[cur][bit]) ch[cur][bit] = ++id;
	
		cur = ch[cur][bit];
		mn[cur] = min(mn[cur], ind);
	
		// cout << "cur " << cur << ' ' << ind << endl;
	}
}

int g(int A, int B) {
	int cur = 0, ans = (int)1e9;
	for (int i = lg - 1; i >= 0; i--) {
		int a = (A >> i) & 1, b = (B >> i) & 1, z = -1;
		for (int j = 0; j < 2; j++) {
			if (!~ch[cur][j]) continue;

			if ((b ^ j) == a) z = ch[cur][j];
			else if ((b ^ j) > a) ans = min(ans, mn[ch[cur][j]]);
		}

		if (!~z) break;

		cur = z;
	}

	return ans;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, X;
	cin >> n >> X;

	mn.assign(n * lg, (int)1e9);
	ch.assign(n * lg, vector<int>(2, -1));

	add(0, 0);

	int hr = 0, L = 0, K = 0;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;

		hr ^= x;

		int l = g(X, hr);

		if (K < i - l) {
			L = l; K = i - l;
		}

		add(hr, i);
	}

	cout << L + 1 << ' ' << K;
}

• Subtask 1: 0 / 100