Submission #361054

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
361054	2021-01-28T09:48:45 Z	SeDunion	XOR (IZhO12_xor)	C++17	100 / 100	117 ms	22472 KB

xor

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

// p[i] ^ p[j] >= x
//
// p[j] >= x ^ p[i]
//
const int LOG = 31;

int p[N], s[N * LOG][2], r, f[N * LOG];

void add(int x, int i) {
	int v = 0;
	for (int bit = LOG - 1 ; bit >= 0 ; -- bit) {
		int u = !!(x & (1 << bit));
		if (!s[v][u]) {
			s[v][u] = ++r;
			f[s[v][u]] = i;
		}
		v = s[v][u];
	}
}

pair<int,int> Ans;

void relax(int x, int i, int k) {
	int v = 0;
	for (int bit = LOG - 1 ; bit >= 0 ; -- bit) {
		int u = !!(x & (1 << bit));
		int q = !!(k & (1 << bit));
		if (q == 0) {
			if (s[v][u^1]) {
				//cout << i << " " << f[s[v][u^1]] << "\n";
				Ans = max(Ans, {i - f[s[v][u^1]], -(f[s[v][u^1]] + 1)});
			}
		}
		if (!s[v][q^u]) return;
		v = s[v][q^u];
	}
	//cout << i << " " << f[v] << "\n";
	Ans = max(Ans, {i - f[v], -(f[v] + 1)});
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 1, a ; i <= n ; ++ i) {
		cin >> a;
		p[i] = p[i - 1] ^ a;
		//cout << p[i] << " \n"[i == n];
	}
	add(0, 0);
	for (int i = 1 ; i <= n ; ++ i) {
		relax(p[i], i, k);
		add(p[i], i);
	}
	//if (Ans.first == 0) return cout << -1, 0;
	cout << -Ans.second << " " << Ans.first;
}

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	6 ms	1004 KB	Output is correct
6	Correct	7 ms	1004 KB	Output is correct
7	Correct	8 ms	1004 KB	Output is correct
8	Correct	8 ms	1132 KB	Output is correct
9	Correct	40 ms	10732 KB	Output is correct
10	Correct	38 ms	10732 KB	Output is correct
11	Correct	37 ms	10604 KB	Output is correct
12	Correct	38 ms	10732 KB	Output is correct
13	Correct	39 ms	10732 KB	Output is correct
14	Correct	41 ms	10732 KB	Output is correct
15	Correct	41 ms	10732 KB	Output is correct
16	Correct	41 ms	10732 KB	Output is correct
17	Correct	114 ms	22472 KB	Output is correct
18	Correct	114 ms	22380 KB	Output is correct
19	Correct	117 ms	22380 KB	Output is correct
20	Correct	111 ms	22380 KB	Output is correct