Cod sursa(job #442926)

Utilizator nandoLicker Nandor nando Data 15 aprilie 2010 18:19:04
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>

FILE* fin=fopen("xormax.in","r");
FILE* fout=fopen("xormax.out","w");

#define MAXL 30
#define MAXN 100005
#define INF 0x3f3f3f3f
#define TEST(a,b) (((a)&(1<<(b)))!=0)
#define max(a,b) (((a)>(b))?(a):(b))

struct nod{
	nod(){
		key=INF,son[0]=son[1]=NULL;
	}
	int key;
	nod* son[2];
}* trie=new nod();


void add(int val,int pos){
	int bit;
	nod* ptr=trie;

	val<<=1;
	for(int i=MAXL;i;--i){
		bit=TEST(val,i);
		if(!ptr->son[bit]){
			ptr->son[bit]=new nod();
		}
		ptr=ptr->son[bit];
	}

	ptr->key=pos;
}

int find(int val){
	bool bit;
	nod* ptr=trie;
	
	val<<=1;
	for(int i=MAXL;i;--i){
		bit=TEST(val,i);
		if(!ptr->son[!bit]){
			ptr=ptr->son[bit];
		}else{
			ptr=ptr->son[!bit];
		}
	}

	return ptr->key;
}

int v[MAXN];

int main(){
	int n,beg=0,end=0,maxv=-1,t;
	fscanf(fin,"%d\n",&n);
	
	for(int i=1;i<=n;i++){
		fscanf(fin,"%d ",&t);
		v[i]=v[i-1]^t;
	}

	add(0,0);
	for(int i=1;i<=n;i++){
		t=find(v[i]);
		if((v[t]^v[i])>maxv){
			maxv=v[t]^v[i];
			end=i,beg=t;
		}
		add(v[i],i);
	}

	fprintf(fout,"%d %d %d\n",maxv,beg+1,end);

	fclose(fin);
	fclose(fout);
	return 0;
}