Cod sursa(job #592723)

Utilizator rudarelLup Ionut rudarel Data 30 mai 2011 08:12:03
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<stdio.h>
 
#define maxN 100005
#define bytmax 25
 
FILE*f=fopen("xormax.in","r");
FILE*g=fopen("xormax.out","w");
 
int n,i,A[maxN],b,x,y,q,poz,xormax = -1,pozmax1,pozmax2;
 
struct Trie{
    int poz;
    Trie *Byt[2];
    Trie () {
        poz = 0;
        Byt[0] = Byt[1] = NULL;
    }
};
 
Trie *r = new Trie;
 
void insert ( Trie *nod , int nb ){
    if ( !(nb + 1) ){
        return ;
    }
     
    b = (x & ( 1 << nb )) != 0;
    if ( nod->Byt[b] == NULL ){
        nod->Byt[b] = new Trie;
    }
    (nod->Byt[b])->poz = i;
     
    insert( nod->Byt[b] , nb - 1 );
}
 
int query ( Trie *nod , int nb ){
    if ( !(nb + 1) ){
        poz = nod -> poz;
        return 0;
    }
     
    b = (x & ( 1 << nb )) != 0;
    if ( nod->Byt[!b] )
        return ( (1 << nb) + query( nod->Byt[!b] , nb - 1 ) );
    else
        if ( nod->Byt[b] )
            return ( query( nod->Byt[b] , nb - 1 ) );
     
    poz = nod -> poz;
     
    return 0;
}
 
 
int main () {
     
    fscanf(f,"%d",&n);
     
    for ( i = 1 ; i <= n ; ++i ){
       fscanf(f,"%d",&A[i]);
    }
     
    i = 0; insert(r,bytmax-2);
     
    for ( i = 1 ; i <= n ; ++i ){
        x = A[i] ^ y;
         
        q = query(r,bytmax-2);
        if ( q > xormax ){
            xormax = q;
            pozmax1 = poz + 1;
            pozmax2 = i;
        }
         
        insert(r,bytmax-2);
        y = x;
    }
     
    fprintf(g,"%d %d %d\n",xormax,pozmax1,pozmax2);
     
    fclose(f);
    fclose(g);
     
    return 0;
}