Cod sursa(job #196901)

Utilizator mariusdrgdragus marius mariusdrg Data 29 iunie 2008 23:47:17
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<stdio.h>
#include<algorithm>


const int maxn = 100100,maxst = 2000000;

int ANS,TR[maxst][2],SIR[maxst];
int N,NRST,S[maxn],A[maxn];

int caut(int val)
{
        memset(S,0,sizeof(S));
        int le = 21;
        for(int l = 0;(1 << l) <= val; ++l)
                S[le - l] = ((val & (1 << l)) != 0);
        int st = 0;
        for(int i = 0;i < le; ++i)
                if (TR[st][S[i] ^ 1]) st = TR[st][S[i] ^ 1];
                        else st = TR[st][S[i]];
        return SIR[st];
}

void ad(int poz)
{
        memset(S,0,sizeof(S));
        int le = 21;
        for(int l = 0;(1 << l) <= A[poz]; ++l)
                S[le - l] = ((A[poz] & (1 << l)) != 0);
        int st = 0;
        for(int i = 0;i < le; ++i)
        {
                if (!TR[st][S[i]]) TR[st][S[i]] = ++NRST;
                st = TR[st][S[i]];
        }
        SIR[st] = poz;
}

int main()
{
        freopen("xormax.in","r",stdin);
        freopen("xormax.out","w",stdout);
        scanf("%d",&N);
        for(int i = 1;i <= N; ++i)
                scanf("%d",&A[i]);
        for(int i = 1;i <= N; ++i)
                A[i] ^= A[i - 1];
        int poz1 = 0,poz2 = 0;
        ad(0);
        for(int i = 1;i <= N; ++i)
        {
                int x = caut(A[i]);
                if (ANS < A[i] ^ A[x]) {ANS = A[i] ^ A[x];poz1 = i;poz2 = x + 1;}
                ad(i);
        }

        printf("%d %d %d\n",ANS,poz2,poz1);
        return 0;
}