Cod sursa(job #384788)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 20 ianuarie 2010 22:44:11
Problema Xor Max Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<stdio.h>
#define infile "xormax.in"
#define outfile "xormax.out"
#define nmax (100*1001)
#define hmax 22
struct trie
{
	int poz[2]; //pozitia catre cei 2 fii
	int pmax; //pozitia maxima din sir ce se termina cu acest xor (doar pentru frunze)
} t[nmax*hmax];
int v[nmax]; //vectorul cu numerele
int n; //numarul de elemente
int nr; //numarul de noduri alee trie-ului
int max,start,stop; //valoarea maxima, respectiv capetele secventei

void push(int rad, int val, int poz, int bit)
{
	if(bit<0) t[rad].pmax=poz;
	else
	{
		if(!t[rad].poz[(val>>bit)&1]) ++nr,t[rad].poz[(val>>bit)&1]=nr;
		push(t[rad].poz[(val>>bit)&1],val,poz,bit-1);
	}
}

int query(int rad, int val, int bit, int *poz)
{
	if(bit<0) { *poz=t[rad].pmax; return 0; }
	if(t[rad].poz[!((val>>bit)&1)]) return (1<<bit) + query(t[rad].poz[!((val>>bit)&1)],val,bit-1,poz);
	return query(t[rad].poz[(val>>bit)&1],val,bit-1,poz);
}

void read()
{
	int i;
	scanf("%d\n",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
}

void solve()
{
	int i,j,k,l;
	
	//luam separat primul element
	max=j=v[1]; start=stop=1;
	push(0,j,2,hmax-1);
	
	for(i=2;i<=n;i++)
	{
		j=j^v[i];
		k=query(0,j,hmax-1,&l);
		if(k>max) max=k,start=l,stop=i;
		push(0,j,i+1,hmax-1);
	}
}

void write()
{
	printf("%d %d %d\n",max,start,stop);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	solve();
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}