Submission #361019

#	Time	Username	Problem	Language	Result	Execution time	Memory
361019		dimashii	XOR (IZhO12_xor)	C++17	100 / 100	228 ms	24576 KiB

xor

#include <bits/stdc++.h>
 
#define ll long long
 
using namespace std;
 
const int mxN = 1e6 + 45, mod = 1e9 + 7, mxB = 29;
const ll inf = 2e18 + 43;
 
int n, x, a[mxN], sz = 1, dp[mxN * 30];
 
struct trie {
	int nxt[2] = {0, 0};
} t[mxN * 30];
 
void add(int val, int i, int v = 1, int depth = 0) {
	if (depth > mxB) {
		if (!dp[v]) dp[v] = i;
		return;
	}
	if ((val >> (mxB - depth)) & 1) {
		if (!t[v].nxt[1]) t[v].nxt[1] = ++sz;
		add(val, i, t[v].nxt[1], depth + 1);
	}else {
		if (!t[v].nxt[0]) t[v].nxt[0] = ++sz;
		add(val, i, t[v].nxt[0], depth + 1);
	}
	dp[v] = min(dp[t[v].nxt[0]], dp[t[v].nxt[1]]);
}
 
int get(int val, int k, int v = 1, int depth = 0) {
	if (depth > mxB) return (!dp[v] ? mod : dp[v]);
	int ans = n + 1;
	if (!((k >> (mxB - depth)) & 1)) {
		if ((val >> (mxB - depth)) & 1) {
			ans = min(ans, dp[t[v].nxt[0]]);
			if (t[v].nxt[1]) {
				int new_val = (val ^ (1 << (mxB - depth)));
				ans = min(ans, get(new_val, k, t[v].nxt[1], depth + 1));
			}
		}
		else {
			ans = min(ans, dp[t[v].nxt[1]]);
			if (t[v].nxt[0]) ans = min(ans, get(val, k, t[v].nxt[0], depth + 1));
		}	
	}else {
		int new_k = (k ^ (1 << (mxB - depth)));
		if ((val >> (mxB - depth)) & 1) {
			if (t[v].nxt[0]) {
				int new_val = (val ^ (1 << (mxB - depth)));
				ans = min(ans, get(new_val, new_k, t[v].nxt[0], depth + 1));
			}
		}
		else {
			if (t[v].nxt[1]) ans = min(ans, get(val, new_k, t[v].nxt[1], depth + 1));
		}
	}
	return ans;
}
 
int main() {                            	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> x;
	for (int i = 1; i <= n; ++i) 
		cin >> a[i], a[i] ^= a[i - 1];
	dp[0] = n + 1;
	add(0, 0);
	int k, mx = -1;
	for (int i = 1; i <= n; ++i) {
		int j = get(a[i], x);
		if (mx < i - j) {
			mx = i - j;
			k = j + 1;
		}
		add(a[i], i);
	}
	if (mx == -1) {
		cout << -1;
		return 0;
	}
	cout << k << ' ' << mx;
	return 0;
}

• Subtask 1: 100 / 100