Cod sursa(job #206675)

Utilizator MisterXGrigore MisterX Data 8 septembrie 2008 18:16:59
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 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;   
}