Cod sursa(job #781644)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 24 august 2012 19:44:06
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<fstream>
using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

int N,i,j,z,a[100001],s[100001],maxim,pozi,pozf,c,next;

struct trie{
int index;
trie* digit[2];
trie()
  {index=0;
   digit[0]=0; digit[1]=0;}
};
trie* t=new trie;

void add(int val, int id)
{trie* nod=t;
for(int psi=20; psi>=0; psi--)
 {c=val&(1<<psi);
  if(c) 
    next=1;
  else   
    next=0;
  if(nod->digit[next]==0)
    nod->digit[next]=new trie; 
  nod=nod->digit[next];
 }
 nod->index=id;
}

int find(int val)
{trie* nod=t;
for(int psi=20; psi>=0; psi--)
{c=val&(1<<psi);
 if(c)  
   {next=0;
    if(nod->digit[next]==0)
       next=1;
    }
 else
   {next=1;
    if(nod->digit[next]==0)
       next=0;
    }      
 nod=nod->digit[next];
}
return nod->index;
}

int main()
{f>>N;
f>>s[1];
add(s[1],1);
maxim=s[1];
pozi=1;  pozf=1;
for(i=2; i<=N; i++)
{f>>z;
 s[i]=s[i-1]^z;
 j=find(s[i]);
 if((s[j]^s[i])>maxim)
   {maxim=s[j]^s[i];
    pozi=j+1;
    pozf=i;}   
 add(s[i],i);
 if(s[i]>maxim)
   {maxim=s[i];
    pozi=1;
    pozf=i;}
}

g<<maxim<<" "<<pozi<<" "<<pozf<<endl;

f.close();
g.close();
return 0;}