Submission #361054

#	Time	Username	Problem	Language	Result	Execution time	Memory
361054		SeDunion	XOR (IZhO12_xor)	C++17	100 / 100	117 ms	22472 KiB

xor

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

// p[i] ^ p[j] >= x
//
// p[j] >= x ^ p[i]
//
const int LOG = 31;

int p[N], s[N * LOG][2], r, f[N * LOG];

void add(int x, int i) {
	int v = 0;
	for (int bit = LOG - 1 ; bit >= 0 ; -- bit) {
		int u = !!(x & (1 << bit));
		if (!s[v][u]) {
			s[v][u] = ++r;
			f[s[v][u]] = i;
		}
		v = s[v][u];
	}
}

pair<int,int> Ans;

void relax(int x, int i, int k) {
	int v = 0;
	for (int bit = LOG - 1 ; bit >= 0 ; -- bit) {
		int u = !!(x & (1 << bit));
		int q = !!(k & (1 << bit));
		if (q == 0) {
			if (s[v][u^1]) {
				//cout << i << " " << f[s[v][u^1]] << "\n";
				Ans = max(Ans, {i - f[s[v][u^1]], -(f[s[v][u^1]] + 1)});
			}
		}
		if (!s[v][q^u]) return;
		v = s[v][q^u];
	}
	//cout << i << " " << f[v] << "\n";
	Ans = max(Ans, {i - f[v], -(f[v] + 1)});
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 1, a ; i <= n ; ++ i) {
		cin >> a;
		p[i] = p[i - 1] ^ a;
		//cout << p[i] << " \n"[i == n];
	}
	add(0, 0);
	for (int i = 1 ; i <= n ; ++ i) {
		relax(p[i], i, k);
		add(p[i], i);
	}
	//if (Ans.first == 0) return cout << -1, 0;
	cout << -Ans.second << " " << Ans.first;
}

• Subtask 1: 100 / 100