Submission #342061

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
342061	2021-01-01T09:01:59 Z	dimashii	XOR (IZhO12_xor)	C++17	100 / 100	201 ms	24428 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	9 ms	1132 KB	Output is correct
6	Correct	12 ms	1260 KB	Output is correct
7	Correct	12 ms	1260 KB	Output is correct
8	Correct	14 ms	1260 KB	Output is correct
9	Correct	70 ms	11500 KB	Output is correct
10	Correct	71 ms	11500 KB	Output is correct
11	Correct	69 ms	11500 KB	Output is correct
12	Correct	68 ms	11500 KB	Output is correct
13	Correct	69 ms	11520 KB	Output is correct
14	Correct	72 ms	11520 KB	Output is correct
15	Correct	68 ms	11444 KB	Output is correct
16	Correct	71 ms	11500 KB	Output is correct
17	Correct	199 ms	24300 KB	Output is correct
18	Correct	201 ms	24368 KB	Output is correct
19	Correct	201 ms	24428 KB	Output is correct
20	Correct	200 ms	24320 KB	Output is correct