Cod sursa(job #196906)

Utilizator mariusdrgdragus marius mariusdrg Data 30 iunie 2008 00:11:20
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<stdio.h>
#include<algorithm>


const int maxn = 100100,maxst = 3000000;

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

int caut(int val)
{
        memset(S,0,sizeof(S));
        int le = 22;
        for(int l = 0;(1 << l) <= val; ++l)
                S[le - l - 1] = ((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 = 22;
        for(int l = 0;(1 << l) <= A[poz]; ++l)
                S[le - l - 1] = ((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);
        }
        if (N == 1) {ANS = A[1];poz2 = 1;poz1 = 1;}
        printf("%d %d %d\n",ANS,poz2,poz1);
        return 0;
}