Submission #4806

#	Time	Username	Problem	Language	Result	Execution time	Memory
4806		cki86201	XOR (IZhO12_xor)	C++98	100 / 100	136 ms	92892 KiB

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 / 100