Submission #498895

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
498895	2021-12-26T14:14:11 Z	Gurban	XOR (IZhO12_xor)	C++17	100 / 100	146 ms	52692 KB

xor

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn=3e5+5;
const int B = 31;
int n,x,sz = 1;
int dp[maxn * B];
int to[maxn * B][2];

void add(int v,int idx){
	int now = 0;
	dp[0] = min(dp[0],idx);
	for(int i = B-1;i >= 0;i--){
		int xx = (v >> i) & 1;
		if(!to[now][xx]) to[now][xx] = sz++;
		
		now = to[now][xx];
		dp[now] = min(dp[now],idx);
	}
}

int tap(int v){
	int now = 0;
	int cp = 1e9;
	bool tr = 1;
	for(int i = B-1;i >= 0;i--){
		int a = (v >> i) & 1;
		int b = (x >> i) & 1;
		if(!b and to[now][a ^ 1]) cp = min(cp,dp[to[now][a^1]]);
		
		if(to[now][a ^ b]) now = to[now][a^b];
		else {
			tr = 0;
			break;
		}
	}
	if(tr) cp = min(cp,dp[now]);
	return cp;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> x;
	memset(dp, 127, sizeof dp);
	int nw = 0;
	int ans = 0;
	int ii = -1,k = -1;
	add(0,0);
	for(int i = 1;i <= n;i++){ 
		int a; cin >> a;
		nw ^= a;
		add(nw,i);
		int ind = tap(nw);
		if(ans < i - ind){
			ans = i - ind;
			ii = ind + 1;
			k = i + 1 - ii;
		}
	}
	cout<<ii<<' '<<k;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	36684 KB	Output is correct
2	Correct	16 ms	36652 KB	Output is correct
3	Correct	20 ms	36648 KB	Output is correct
4	Correct	16 ms	36676 KB	Output is correct
5	Correct	21 ms	37064 KB	Output is correct
6	Correct	22 ms	37204 KB	Output is correct
7	Correct	22 ms	37192 KB	Output is correct
8	Correct	23 ms	37416 KB	Output is correct
9	Correct	53 ms	44124 KB	Output is correct
10	Correct	67 ms	44112 KB	Output is correct
11	Correct	69 ms	43988 KB	Output is correct
12	Correct	53 ms	44060 KB	Output is correct
13	Correct	53 ms	44104 KB	Output is correct
14	Correct	48 ms	44108 KB	Output is correct
15	Correct	61 ms	44068 KB	Output is correct
16	Correct	62 ms	44040 KB	Output is correct
17	Correct	146 ms	52692 KB	Output is correct
18	Correct	140 ms	52632 KB	Output is correct
19	Correct	142 ms	52680 KB	Output is correct
20	Correct	141 ms	52640 KB	Output is correct