Cod sursa(job #1162631)

Utilizator PatrikStepan Patrik Patrik Data 31 martie 2014 21:42:06
Problema Xor Max Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
    #include<cstdio>
    using namespace std;
    #define NMAX 100001
    int N , v[NMAX] , s[NMAX][22] , poz , best = -1 , nr;
    struct nod
    {
        nod *fiu[2];
        nod()
        {
            fiu[0] = fiu[1] = 0;
        }
    };
    nod *rad = new nod();

    void query(int v[]);
    void add(nod *q,int v[] , int poz);

    int main()
    {
        int x;
        freopen("xormax.in" , "r" , stdin );
        freopen("xormax.out" , "w" , stdout );
        nod *q = rad;
        for(int i = 1 ; i <= 21 ; ++i , q = q->fiu[0])
            q->fiu[0] = new nod();
        scanf("%d" , &N );
        for(int i = 1 ; i <= N ; ++i )
        {
            scanf("%d" , &v[i]);
            v[i] = v[i]^v[i-1];
            int x = v[i];
            for(int j = 21 ; j ; j-- , x/=2 )
                s[i][j] = x%2;
            nr = 0;
            query(s[i]);
            if((nr^v[i]) > best)
            {
                best = (nr^v[i]);
                poz = i;
            }
            add(rad,s[i],0);
        }
        printf("%d " , best);
        for(int i = 0 ; i < poz ; ++i )
            if((v[i]^v[poz]) == best )
            {
                printf("%d %d\n" , i+1 , poz);
                break;
            }
        return 0;
    }

    void query(int v[])
    {
        nod *q = rad;
        for(int i = 1 ; i <= 21 ; ++i )
            if(q->fiu[1-v[i]])
            {
                nr = nr*2+1-v[i];
                q = q->fiu[1-v[i]];
            }
            else
            {
                nr = nr*2+v[i];
                q = q->fiu[v[i]];
            }
    }

    void add(nod *q , int v[] , int poz)
    {
        if(poz == 21)return;
        if(!q->fiu[v[poz+1]])q->fiu[v[poz+1]] = new nod();
        add(q->fiu[v[poz+1]],v,poz+1);
    }