Cod sursa(job #1312598)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 9 ianuarie 2015 19:19:04
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<cstdio>
#include<cstring>
const int N=100000;
struct Node{
    Node*v[2];
    int val;
    Node(){
        v[0]=0;
        v[1]=0;
    }
};
long long v[N+1];
long long x[N+1];
long long p2[N+1];
int b2[23];
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==22){
        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==22){
        pp=node->val;
        return 0;
    }
    if(node->v[1-b2[p]])
        return p2[21-p]*(1-b2[p])+ask(node->v[1-b2[p]],p+1);
    else
        return p2[21-p]*(b2[p])+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;
}
void lol(){
    int x=0;
    x++;
}
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;
        if(i==5)
            lol();
        desc(x[i]);
        add(t,0);
    }
    long long res=0;
    int ji,jj;
    for(int i=1;i<=n;i++){
        desc(x[i]);
        if(i==11)
            lol();
        long long pol=ask(t,0);
        if(pol^x[i]>res){
            ji=i;
            jj=pp;
            res=pol^x[i];
        }
    }
    printf("%lld %lld %lld",res,min2(ji,jj)+1,max2(ji,jj));
    return 0;
}