Cod sursa(job #996043)

Utilizator andrettiAndretti Naiden andretti Data 10 septembrie 2013 20:45:17
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define maxn 100005
#define maxb 20
using namespace std;

int n,sol=-1,s,e;
int solc,sc;
int sum[maxn];

struct trie
{
    trie *son[2];
    int pos;
    trie() {son[0]=son[1]=NULL; pos=0;}
} *r;

void add(int nr,int inde)
{
    trie *node=r;
    int ind;
    for(int i=maxb;i>=0;i--)
    {
        ind=((nr>>i)&1);
        if(node->son[ind]==NULL) node->son[ind]=new trie();
        node=node->son[ind];
    }
    node->pos=inde;
}

int search(int nr)
{
    trie *node=r;
    int ind;
    for(int i=maxb;i>=0;i--)
    {
        ind=((nr>>i)&1);
        if(node->son[!ind]!=NULL) node=node->son[!ind];
        else node=node->son[ind];
    }
    return node->pos;
}

void read()
{
    int a;
    r=new trie();
    scanf("%d",&n);

    add(0,0);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        sum[i]=(sum[i-1]^a);

        sc=search(sum[i]);
        solc=(sum[i]^sum[sc]);
        if(solc>sol) sol=solc,s=sc+1,e=i;
        add(sum[i],i);
    }
}

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);

    read();
    printf("%d %d %d",sol,s,e);

    fclose(stdin);
    fclose(stdout);
    return 0;
}