Cod sursa(job #197016)

Utilizator devilkindSavin Tiberiu devilkind Data 30 iunie 2008 19:37:48
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define NMAX 100002
#define LMAX 22
#define mp make_pair
#define ff first
#define ss second

long int a[NMAX];
long int n,nr;
pair<int,int> FR[1 << LMAX];
long int TR[ 1 << LMAX][2];
pair<int, pair<int,int> > sol,crt;

void baga_tr(long int nod, long int v, long int poz, long int bit)
{
	long int b;

	if (bit==-1) {FR[nod]=mp(v,poz);return;}

	b=v&(1 << bit);
        if (b) b=1;

	if (TR[nod][b]==0) TR[nod][b]=++nr;
	baga_tr(TR[nod][b],v,poz,bit-1);
}

void query(long int nod, long int v,long int poz, long int bit)
{
	long int x,y,b;

	if (bit==-1)
	{
		x=FR[nod].ff;y=FR[nod].ss;
		if ( (v^x) >sol.ff) sol=mp(v^x, mp(y+1,poz) );
                return;
	}

	b=v&(1<<bit);
        if (b) b=1;
        
	if (TR[nod][!b]) query(TR[nod][!b],v,poz,bit-1);
		else query(TR[nod][b],v,poz,bit-1);
}

int main()
{
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);
	
	long int i;

	scanf("%ld ",&n);

	for (i=1;i<=n;i++)
	{
		scanf("%ld",&a[i]);
		a[i]=a[i-1]^a[i];
	}

	nr=1;
	baga_tr(1,0,0,20);

	for (i=1;i<=n;i++)
	{
		query(1,a[i],i,20);
		baga_tr(1,a[i],i,20);
	}
	printf("%ld %ld %ld",sol.ff,sol.ss.ff,sol.ss.ss);
	return 0;
}