Cod sursa(job #2143428)

Utilizator ovidius11Stiriu Ovidius ovidius11 Data 25 februarie 2018 22:22:09
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h> 
#define maxim(a,b) ((a)>(b) ? (a) : (b))
#define MAXBIT 20 
int sol,rez=-1,n,s[100005]; 
struct nod {
int poz;
nod *dir[2];
nod() { dir[0]=dir[1]=0; }
};
nod *rad; 
void insert(int val, int k, nod* r, int pi){
if (k<0){
r->poz=pi;
return;}
int bit=(val&(1<<k))!=0; 
if (r->dir[bit]==0)
r->dir[bit]=new nod();
insert(val, k-1, r->dir[bit], pi);} 
int find(int val,int k,nod* r){
if(k<0)
return r->poz; 
int bit=1-((val&(1<<k))!=0);
if(r->dir[bit]==0)
return find(val,k-1,r->dir[!bit]);
return find(val,k-1,r->dir[bit]);} 
int main (){
int i,val,poz,x=0,y=0; 
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n);
rad=new nod();
insert(0,MAXBIT,rad,0); 
for(i=1;i<=n;i++){
scanf("%d",&val);
s[i]=s[i-1]^val; 
sol=s[poz=find(s[i],MAXBIT,rad)];
if (rez < (sol^s[i])){
rez=(sol^s[i]);
x=poz+1;
y=i;}
insert(s[i],MAXBIT,rad,i);} 
printf("%d %d %d\n",rez,x,y);
return 0;}