Cod sursa(job #670708)

Utilizator GrimpowRadu Andrei Grimpow Data 29 ianuarie 2012 20:44:14
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<fstream>
#include<algorithm>
#include<string.h>

using namespace std;
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()
{
        ifstream f("xormax.in");
        ofstream g("xormax.out");
        f>>N;
        for(int i = 1;i <= N; ++i)
                f>>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;}
        g<<ANS<<' '<<poz2<<' '<<poz1;
        return 0;
}