Cod sursa(job #1532868)

Utilizator binicBinica Nicolae binic Data 21 noiembrie 2015 18:36:33
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,x,ok,rasp,ma,k,p1,p2,a[100004];

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

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