Submission #4806

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4806	2014-01-04T09:22:52 Z	cki86201	XOR (IZhO12_xor)	C++	100 / 100	136 ms	92892 KB

xor

#include<stdio.h>
#include<algorithm>
using namespace std;

int N,U;
int Trie[250020*31][2],Len;
int M[250020*31], inp[250020];
int ans[2];

int main(){
	scanf("%d%d",&N,&U);
	int i;
	for(i=1;i<=N;i++){
		int x;
		scanf("%d",&x);
		inp[i] = inp[i-1] ^ x;
	}
	for(i=0;i<=N;i++){
		int now = 0;
		for(int j=30;j>=0;j--){
			int tmp = (inp[i]&1<<j)?1:0;
			if(!Trie[now][tmp])Trie[now][tmp] = ++Len;
			now = Trie[now][tmp];
			M[now] = i;
		}
	}
	for(i=0;i<N;i++){
		int now = 0, mx = 0;
		for(int j=30;j>=0;j--){
			int tmp = (inp[i]&1<<j);
			int u = (U&1<<j);
			if(!u)mx = max(mx, M[Trie[now][!tmp]]);
			if(!(now = Trie[now][(u^tmp)?1:0]))break;
		}
		mx = max(mx, M[now]);
		if(ans[1] < mx-i)ans[1]=mx-i,ans[0]=i+1;
	}
	printf("%d %d",ans[0],ans[1]);
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	92892 KB	Output is correct
2	Correct	0 ms	92892 KB	Output is correct
3	Correct	0 ms	92892 KB	Output is correct
4	Correct	0 ms	92892 KB	Output is correct
5	Correct	8 ms	92892 KB	Output is correct
6	Correct	12 ms	92892 KB	Output is correct
7	Correct	8 ms	92892 KB	Output is correct
8	Correct	8 ms	92892 KB	Output is correct
9	Correct	40 ms	92892 KB	Output is correct
10	Correct	52 ms	92892 KB	Output is correct
11	Correct	52 ms	92892 KB	Output is correct
12	Correct	40 ms	92892 KB	Output is correct
13	Correct	52 ms	92892 KB	Output is correct
14	Correct	44 ms	92892 KB	Output is correct
15	Correct	40 ms	92892 KB	Output is correct
16	Correct	44 ms	92892 KB	Output is correct
17	Correct	132 ms	92892 KB	Output is correct
18	Correct	124 ms	92892 KB	Output is correct
19	Correct	128 ms	92892 KB	Output is correct
20	Correct	136 ms	92892 KB	Output is correct