Cod sursa(job #1719347)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 19 iunie 2016 13:34:03
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<cstdio>
#define MAXN 100010
#define MAXLOG 22
using namespace std;
int xorSum[MAXN];
struct Trie{
    int index;
    Trie *sons[2];
    Trie(){
        index=0;
        sons[0]=sons[1]=NULL;
    }
};
Trie *root;
void Insert(Trie *node,int value,int index){
    int i;
    bool bit;
    for(i=MAXLOG;i>=0;i--){
        bit=(value&(1<<i));
        if(node->sons[bit]==NULL)
            node->sons[bit]=new Trie();
        node=node->sons[bit];
    }
    node->index=index;
}
int Find(Trie *node,int value){
    int i;
    bool bit;
    for(i=MAXLOG;i>=0;i--){
        bit=(value&(1<<i));
        if(node->sons[!bit]!=NULL)
            node=node->sons[!bit];
        else
            node=node->sons[bit];
    }
    return node->index;
}
int main(){
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    int n,x,i,answer=-1,left,right,best;
    root=new Trie();
    scanf("%d",&n);
    Insert(root,0,0);
    for(i=1;i<=n;i++){
        scanf("%d",&x);
        xorSum[i]=xorSum[i-1]^x;
        best=Find(root,xorSum[i]);
        if(xorSum[i]^xorSum[best]>answer){
            answer=xorSum[i]^xorSum[best];
            left=best+1;
            right=i;
        }
        Insert(root,xorSum[i],i);
    }
    printf("%d %d %d",answer,left,right);
    return 0;
}