Submission #361019

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
361019	2021-01-28T09:24:53 Z	dimashii	XOR (IZhO12_xor)	C++17	100 / 100	228 ms	24576 KB

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.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	10 ms	1132 KB	Output is correct
6	Correct	12 ms	1260 KB	Output is correct
7	Correct	13 ms	1260 KB	Output is correct
8	Correct	14 ms	1260 KB	Output is correct
9	Correct	68 ms	11500 KB	Output is correct
10	Correct	74 ms	11500 KB	Output is correct
11	Correct	67 ms	11500 KB	Output is correct
12	Correct	68 ms	11500 KB	Output is correct
13	Correct	71 ms	11500 KB	Output is correct
14	Correct	68 ms	11500 KB	Output is correct
15	Correct	70 ms	11444 KB	Output is correct
16	Correct	66 ms	11500 KB	Output is correct
17	Correct	202 ms	24428 KB	Output is correct
18	Correct	228 ms	24300 KB	Output is correct
19	Correct	198 ms	24428 KB	Output is correct
20	Correct	200 ms	24576 KB	Output is correct