Submission #342061

#	Time	Username	Problem	Language	Result	Execution time	Memory
342061		dimashii	XOR (IZhO12_xor)	C++17	100 / 100	201 ms	24428 KiB

xor

#include <bits/stdc++.h>

#define fastio ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define ll long long

using namespace std;

const int mxN = 3e5 + 45, mod = 1e9 + 7, mxB = 29;
const ll inf = 2e18 + 43;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

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() {
	//freopen("c.in", "r", stdin);
	//freopen("c.out", "w", stdout);
	fastio;
	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 = 0;
	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);
	}
	cout << k << ' ' << mx;
	return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:82:15: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |  cout << k << ' ' << mx;
      |               ^~~

• Subtask 1: 100 / 100