Cod sursa(job #429876)

Utilizator hendrikHendrik Lai hendrik Data 30 martie 2010 16:12:35
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

#define bmax 22

struct trie{
    int l;
    trie *f[2];
    trie(){
        f[0]=f[1]=0;
        l=0;
    };
};
trie* T;

int n,arr[100010],sum[100010],best,bestL,bestR,ans;

void add(trie *T,int bit,int num,int idx){
    int x;
    x=(num & (1<<bit))>0;
    if (!T->f[x]) T->f[x]=new trie;
    if (bit==0){
        T->f[x]->l=idx;
        return ;
    }
    add(T->f[x],bit-1,num,idx);
}

void ask(trie *T,int bit,int num){
    if (!T->f[0] && !T->f[1]){
        ans=T->l;
        return;
    }
    int x;
    x=(num & (1<<bit))>0;
    if (T->f[1-x]){
        ask(T->f[1-x],bit-1,num);
    }
    else ask(T->f[x],bit-1,num);
}

int main(){
    //FILE *in=stdin;
    //FILE *out=stdout;
    FILE *in=fopen("xormax.in","r");
    FILE *out=fopen("xormax.out","w");
    fscanf(in,"%d",&n);
    for (int i=1;i<=n;i++){
        fscanf(in,"%d",&arr[i]);
    }
    T=new trie();
    sum[1]=arr[1];
    best=sum[1];bestL=0;bestR=1;
    add(T,bmax,sum[1],1);
    for (int i=1;i<=n;i++){
        sum[i]=sum[i-1]^arr[i];
        ask(T,bmax,sum[i]);
        if ((sum[i]^sum[ans])>best){
            best=sum[i]^sum[ans];
            bestL=ans;
            bestR=i;
        }
        add(T,bmax,sum[i],i);
    }
    fprintf(out,"%d %d %d\n",best,bestL+1,bestR);
    //system("pause");
    return 0;
}