Cod sursa(job #75718)

Utilizator mega_bit8Badita Robert mega_bit8 Data 5 august 2007 00:29:24
Problema Xor Max Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.96 kb
//---------------------------------------------------------------------------
//#pragma option -Od
#include <stdio.h>
//---------------------------------------------------------------------------
typedef struct node {
        int     pos;
        struct node     *son[2];
} *trie;
//---------------------------------------------------------------------------
typedef unsigned int uint;
#define MAX_N   100000
#define MAX_B   21
//---------------------------------------------------------------------------
node    pool[MAX_N* MAX_B];
int     pool_pos= 0;
uint    X[MAX_N+ 1];
//---------------------------------------------------------------------------
#define xor_sum(L, R)   ( X[(R)+ 1] ^ X[L] )
#define A(I)            xor_sum(I, I)
//---------------------------------------------------------------------------
int     maxim(int A, int B)
{
        if (B> A)
                return  B;
        return  A;
}
//---------------------------------------------------------------------------
trie    add(trie T, uint X, int bit_pos, int pos)
{       //returns the new root...
        if (T== NULL) {
                T= &pool[pool_pos++];
                T->pos= pos;
                T->son[0]= T->son[1]= NULL;
        }
        if (bit_pos< 0)
                return  T;
        int     K= (X>> bit_pos) & 1;
        T->son[K]= add(T->son[K], X, bit_pos- 1, pos);
        return  T;
}
//---------------------------------------------------------------------------
int     get_start_pos(trie T, uint X, int bit_pos, int pos)
{       //returns maximum start pos
        if (T== NULL)
                return  pos;    //returns best pos found so far...
        int     K= (X>> bit_pos) & 1;
        trie    S= T->son[K ^ 1];
        if (/*K== 0 && */S!= NULL)
                pos= S->pos;    //in acest caz castigam un bit...
        if (S== NULL)
                S= T->son[K];
//        if (S!= NULL)
//                pos= maxim(pos, S->pos);        //cautam pos cat mai mare...
        return  get_start_pos(S, X, bit_pos -1, pos);
}
//---------------------------------------------------------------------------
void    xormax()
{
        FILE    *F= fopen("xormax.in", "rt");
        int     N;
        fscanf(F, "%u", &N);
        trie    root= NULL;
        uint    max= 0;
        int     max_start= 0,
                max_end= 0;
        /*
                La fiecare pas se cauta 'spos' cel mai mare a.i.
                X[I+ 1] xor X[spos] sa fie maxim...
        */
        X[0]= 0;
        for (int I= 0; I< N; I++) {
                uint    K;
                fscanf(F, "%u", &K);
                X[I+ 1]= X[I] ^ K;
                int     spos= get_start_pos(root, X[I+ 1], MAX_B- 1, 0);
                uint    mx= xor_sum(spos, I);
                if (mx> max) {
                        max= mx;
//                        max_start= spos;
                        max_end= I;
                }
                root= add(root, X[I+ 1], MAX_B- 1, I+ 1);
                //asociaza X[I+ 1] cu pozitia 'I+ 1' pentru ca dupa
                //cautare, in xor_sum, L sa fie egal cu spos...
        }
        fclose(F);

        for (int I= max_end; --I>= 0; )
                if (xor_sum(I, max_end)== max) {
                        max_start= I;
                        break;
                }

        FILE    *G= fopen("xormax.out", "wt");
        fprintf(G, "%u %u %u\n", max, max_start+ 1, max_end+ 1);
        fclose(G);
}
//---------------------------------------------------------------------------
int     vec_xor(int L, int R)
{       //este inlocuit de macro: xor_sum(L, R)
        //X[L  ]= 0..L-1
        //X[R+1]= 0..L..R
        //L..R= X[R+ 1] ^ X[L]
        return  X[R+ 1] ^ X[L];
}
//---------------------------------------------------------------------------
int     main(int argc, char* argv[])
{
        xormax();
        return  0;
}
//---------------------------------------------------------------------------