Submission #405431

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
405431	2021-05-16T11:32:15 Z	ngpin04	XOR (IZhO12_xor)	C++14	100 / 100	208 ms	59416 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	2 ms	320 KB	Output is correct
4	Correct	2 ms	456 KB	Output is correct
5	Correct	8 ms	1864 KB	Output is correct
6	Correct	12 ms	2088 KB	Output is correct
7	Correct	11 ms	2112 KB	Output is correct
8	Correct	12 ms	2192 KB	Output is correct
9	Correct	77 ms	27868 KB	Output is correct
10	Correct	80 ms	28072 KB	Output is correct
11	Correct	72 ms	27844 KB	Output is correct
12	Correct	74 ms	27888 KB	Output is correct
13	Correct	75 ms	27904 KB	Output is correct
14	Correct	78 ms	28200 KB	Output is correct
15	Correct	75 ms	27920 KB	Output is correct
16	Correct	75 ms	27932 KB	Output is correct
17	Correct	193 ms	59332 KB	Output is correct
18	Correct	200 ms	59408 KB	Output is correct
19	Correct	191 ms	59416 KB	Output is correct
20	Correct	208 ms	59400 KB	Output is correct