Submission #405431

#	Time	Username	Problem	Language	Result	Execution time	Memory
405431		ngpin04	XOR (IZhO12_xor)	C++14	100 / 100	208 ms	59416 KiB

xor

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 25e4 + 5; 

struct node {
	node *ptr[2];
	int pos;

	node() {
		ptr[0] = ptr[1] = nullptr;
		pos = 1e9;
	}
};

node *root = new node();

int f[N];
int a[N];
int n,s;

int getbit(int x, int i) {
	return (x >> i) & 1;
}

void add(int x, int val) {
	node *cur = root;
	for (int i = 29; i >= 0; i--) {
		node *&p = cur->ptr[getbit(x, i)];
		if (p == nullptr) 
			p = new node();

		cur = p;
		cur->pos = min(cur->pos, val);
	}
}

int getmin(int x) {
	int res = 1e9;
	node *cur = root;
	for (int i = 29; i >= 0; i--) {
		int b = getbit(x, i);
		if (!f[i] && cur->ptr[b ^ 1] != nullptr) 
			res = min(res, cur->ptr[b ^ 1]->pos);
		
		node *p = cur->ptr[f[i] ^ b];
		if (p == nullptr)
			return res;
		cur = p;
	}
	res = min(res, cur->pos);
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s;
	for (int i = 29; i >= 0; i--)
		f[i] = getbit(s, i);

	for (int i = 1; i <= n; i++)
		cin >> a[i], a[i] ^= a[i - 1];

	int l = 0;
	int r = -1;
	for (int i = 1; i <= n; i++) {
		add(a[i - 1], i - 1);
		int u = getmin(a[i]);
		int v = i;
		if (v - u > r - l || (v - u == r - l && u < l)) {
			l = u;
			r = v;
		}
	}

	cout << l + 1 << " " << r - l;
	return 0;
}

• Subtask 1: 100 / 100