Cod sursa(job #1529051)

Utilizator binicBinica Nicolae binic Data 20 noiembrie 2015 14:44:13
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,x,ok,ras,ma,p1,p2,a[100004];

struct trie
{
    int val;
    trie *urm[2];
    trie()
    {
        val=0;
        urm[0]=0;
        urm[1]=0;
    }
}*init,*nr,*q;

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    for (i=1; i<=n; i++)
    {
        scanf("%d ",&x);
        a[i]=a[i-1]^x;
    }
    init=new trie;
    nr=init;
    for (int j=20; j>=1; j--)
    {
        ok=a[1]&(1<<j);
        q=new trie;
        nr->urm[ok]=q;
        nr=q;
    }
    nr->val=1;
    q=new trie;
    nr->urm[0]=q;
    nr=q;
    for (int i=2; i<=n; i++)
    {
        nr=init;
        for (int j=20; j>=1; j--)
        {
            ok=a[i]&(1<<j);
            if(nr->urm[ok&0]==0)nr=nr->urm[ok];
            else nr=nr->urm[ok&0];
        }
        ras=nr->val;
        if(ma<a[i]^a[ras])
        {
            ma=a[i]^ras;
            p2=i;
            p1=ras+1;
        }
        nr=init;
        for (int j=20; j>=1; j--)
        {
            ok=a[i]&(1<<j);
            q=new trie;
            nr->urm[ok]=q;
            nr=q;
        }
        nr->val=i;
        q=new trie;
        nr->urm[0]=q;
        nr=q;
    }
    printf("%d %d %d",ma,p1,p2);
    return 0;
}