Cod sursa(job #1311060)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 7 ianuarie 2015 17:49:09
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<cstdio>
#include<cstring>
const int N=100000;
struct Node{
    Node*v[2];
    int val;
    Node(){
        v[0]=NULL;
        v[1]=NULL;
    }
};
long long v[N+1];
long long x[N+1];
long long p2[N+1];
int b2[22];
int n;
Node*t=new Node;
void set_p2(){
    p2[0]=1;
    for(int i=1;i<=21;i++)
        p2[i]=2*p2[i-1];
}
int vall;
void add(Node*node,int p){
    char c=b2[p];
    if(p==21){
        node->val=vall;
        return;
    }
    if(node->v[c]==0){
        node->v[c]=new Node;
        node->val=vall;
    }
    add(node->v[c],p+1);
}
int pp;
long long ask(Node*node,int p){
    if(p==21){
        pp=node->val;
        return 0;
    }
    if(node->v[1-b2[p]])
        return p2[21-p]*(1-b2[p])+ask(node->v[b2[p]],p+1);
    else
        return ask(node->v[b2[p]],p+1);
}
void desc(long long x){
    int k=21;
    memset(b2,0,sizeof(b2));
    while(x){
        b2[k--]=x%2;
        x/=2;
    }
}
long long max2(long long a,long long b){
    if(a>b)
        return a;
    return b;
}
long long min2(long long a,long long b){
    if(a<b)
        return a;
    return b;
}
int main(){
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    set_p2();
    for(int i=1;i<=n;i++){
        scanf("%lld",&v[i]);
        x[i]=x[i-1]^v[i];
        vall=i;
        desc(x[i]);
        add(t,0);
    }
    long long res=0;
    int ji,jj;
    for(int i=1;i<=n;i++){
        desc(x[i]);
        long long pol=ask(t,0);
        if(pol^x[i]>res){
            ji=i;
            jj=pp;
            res=pol^x[i];
        }
    }
    printf("%lld %d %d",res,min2(ji,jj),max2(ji,jj));
    return 0;
}