Cod sursa(job #1312600)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 9 ianuarie 2015 19:32:10
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<cstdio>
#include<cstring>
const int N=100000;
struct Node{
    Node*v[2];
    int val;
    Node(){
        v[0]=0;
        v[1]=0;
    }
};
int v[N+1];
int x[N+1];
int 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;
int 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(int x){
    int k=21;
    memset(b2,0,sizeof(b2));
    while(x){
        b2[k--]=x%2;
        x/=2;
    }
}
int max2(int a,int b){
    if(a>b)
        return a;
    return b;
}
int min2(int a,int 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("%d",&v[i]);
        x[i]=x[i-1]^v[i];
        vall=i;
        if(i==5)
            lol();
        desc(x[i]);
    }
    int res=0;
    int ji,jj;
    for(int i=1;i<=n;i++){
        desc(x[i]);
        if(i==11)
            lol();
        int pol=ask(t,0);
        if(pol^x[i]>res){
            ji=i;
            jj=pp;
            res=pol^x[i];
        }
    }
    printf("%d %d %d",res,min2(ji,jj)+1,max2(ji,jj));
    return 0;
}