Submission #250655

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
250655	2020-07-18T15:13:59 Z	srvlt	XOR (IZhO12_xor)	C++14	100 / 100	228 ms	46760 KB

xor

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 250007, k0 = 30;
int n, k, a[n0], T[2][n0 * k0], sz;
int mn[n0 * k0];

void add(int pos) {
	int v = 0, x = a[pos];
	for (int i = k0 - 1; i >= 0; i--) {
		if (!T[x >> i & 1][v])
			T[x >> i & 1][v] = ++sz;
		v = T[x >> i & 1][v];
	}
	mn[v] = min(mn[v], pos);
}

void dfs(int v) {
	for (int i = 0; i < 2; i++) {
		int to = T[i][v];
		if (to) {
			dfs(to);
			mn[v] = min(mn[v], mn[to]);
		}
	}
}

int X;

int get(int v, int cur, int x, int d) {
	if ((cur ^ x) >= k) return mn[v];
	if ((cur ^ x) + (1 << (d + 1)) - 1 < k) return n0;
	int res = n0;
	for (int i = 0; i < 2; i++) {
		int to = T[i][v];
		int bit = (i) ? (1 << d) : 0;
		int bit2 = X & (1 << d); 
		if (to) res = min(res, get(to, cur ^ bit, x ^ bit2, d - 1));
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	memset(& mn, 0x3f, sizeof(mn));
	cin >> n >> k;
	add(0);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] ^= a[i - 1];
		add(i);
	}
	dfs(0);
	int res = 0, ind = -1;
	for (int i = 1; i <= n; i++) {
		X = a[i];
		int l = get(0, 0, 0, k0 - 1);
		if (l < i && i - l > res)
			res = i - l, ind = i;
	}
	cout << ind - res + 1 << ' ' << res;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	29696 KB	Output is correct
2	Correct	15 ms	29696 KB	Output is correct
3	Correct	15 ms	29696 KB	Output is correct
4	Correct	17 ms	29824 KB	Output is correct
5	Correct	23 ms	30208 KB	Output is correct
6	Correct	25 ms	30336 KB	Output is correct
7	Correct	28 ms	30336 KB	Output is correct
8	Correct	27 ms	30416 KB	Output is correct
9	Correct	85 ms	37496 KB	Output is correct
10	Correct	88 ms	37496 KB	Output is correct
11	Correct	77 ms	37624 KB	Output is correct
12	Correct	114 ms	37496 KB	Output is correct
13	Correct	89 ms	37496 KB	Output is correct
14	Correct	87 ms	37496 KB	Output is correct
15	Correct	90 ms	37524 KB	Output is correct
16	Correct	78 ms	37496 KB	Output is correct
17	Correct	212 ms	46712 KB	Output is correct
18	Correct	206 ms	46760 KB	Output is correct
19	Correct	216 ms	46712 KB	Output is correct
20	Correct	228 ms	46712 KB	Output is correct