Mai intai trebuie sa te autentifici.
Cod sursa(job #491245)
Utilizator | Data | 10 octombrie 2010 19:40:26 | |
---|---|---|---|
Problema | Xor Max | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.1 kb |
#include <cstdio>
FILE *in,*out;
struct nod
{
int v;
nod * next[2];
nod()
{
next[0]=next[1]=NULL;
v=0;
}
};
nod * trie;
void add( nod * p, int val,int poz,int adanc)
{
if (adanc<0)
{
p->v=poz;
if (val!=0)
fprintf(stderr,"bug\n");
return ;
}
int x=(bool)(val & (1<<adanc));
if (p->next[x]==NULL)
p->next[x]=new nod;
add(p->next[x],val-(1<<adanc)*x,poz,adanc-1);
}
int search (nod * p, int &rez, int y,int adanc)
{
if (adanc<0)
return p->v;
int x=!(y&(1<<adanc));
if (p->next[x]!=NULL)
{
rez+=(1<<adanc)*x;
return search(p->next[x],rez,y,adanc-1);
}
rez+=(1<<adanc)*(!x);
return search(p->next[!x],rez,y,adanc-1);
}
int main()
{
int n,y,i,x,start,stop,maxv,poz;
in=fopen("xormax.in","r");
out=fopen("xormax.out","w");
fscanf(in,"%d",&n);
trie=new nod;
y=0;
for (i=1;i<=n;i++)
{
fscanf(in,"%d",&x);
y=y^x;
add(trie,y,i,20);
if (i==1)
{
maxv=y;
start=0;
stop=1;
continue;
}
x=0;
poz=search(trie,x,y,20);
if ((x^y)>maxv)
{
maxv=x^y;
start=poz;
stop=i;
}
}
fprintf(out,"%d %d %d\n",maxv,start+1,stop);
fclose(in);
fclose(out);
return 0;
}