Cod sursa(job #847460)

Utilizator test_13testing test_13 Data 3 ianuarie 2013 22:05:42
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <set>
using namespace std;
#define inf 0xffffff
#define Max 100001
#define eps 1e-6

int n,x[Max];
struct dic{ struct dic *f[2]; int idx; dic(){ for(int i=0;i<2;i++)f[i]=NULL; } }*t;

void insert(int x,int idx)
{
	dic *g=t;
	int urm;
	for(int i=21;i>=0;i--)
	{
		if(x&(1<<i))urm=1; else urm=0;
		if(g->f[urm]==NULL)g->f[urm]=new dic;
		g=g->f[urm];
	}
	g->idx=idx;
}

int find(int x)
{
	dic *g=t;
	int urm;
	for(int i=21;i>=0;i--)
	{
		if(x&(1<<i))urm=0; else urm=1;
		if(g->f[urm]==NULL)urm=!urm;
		g=g->f[urm];
	}
	return g->idx;
}

int main()
{
	int bst,p,u,p1;
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);
		scanf("%d",&n);
		t = new dic;
		for(int i=1;i<=n;i++) scanf("%d",&x[i]);
		for(int i=1;i<=n;i++) x[i]^=x[i-1];
		bst=0; p=u=1;
		for(int i=1;i<=n;i++)
		{
			insert(x[i],i);
			p1=find(x[i]);
			if((x[i]^x[p1])>bst)
			{
				bst=x[i]^x[p1];
				p=p1+1;
				u=i;
			}
		}
		printf("%d %d %d\n",bst,p,u);
	return 0;
}