Submission #250655

#	Time	Username	Problem	Language	Result	Execution time	Memory
250655		srvlt	XOR (IZhO12_xor)	C++14	100 / 100	228 ms	46760 KiB

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 / 100