Cod sursa(job #2047573)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 24 octombrie 2017 23:45:40
Problema Xor Max Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <iostream>
#include <stdio.h>

using namespace std;

const int N = 1e5 + 5 ;
const int FIRSTBIT = 22 ;

struct nodTrie{
    int val ;
    nodTrie *fiu[ 2 ] ;

    public: nodTrie(){
        fiu[ 0 ] = NULL ;
        fiu[ 1 ] = NULL ;
    }

};

int noNumbers ;
int valXor [ N ];

nodTrie *root ;

void addValToTrie ( nodTrie *crNod , int crNumIndex , int crBit  ){
    static int valBit ;

    if ( crBit == -1 ){
        crNod->val = crNumIndex ;
        return ;
    }

    valBit = ( ( valXor [ crNumIndex ] & ( 1<<crBit ) ) != 0 ) ;

    if ( crNod->fiu [ valBit ] == NULL  ){
        crNod->fiu [ valBit ] = new nodTrie ;
    }

    addValToTrie ( crNod->fiu[ valBit ] , crNumIndex , crBit - 1 );

}

int findPairInTrie ( nodTrie *crNod , int crNumIndex , int crBit ){
    static int valBit ;

    if ( crBit == -1 ){
        return crNod->val ;
    }


    valBit = ( ( valXor [ crNumIndex ] & ( 1<<crBit ) ) != 0 ) ;

    if ( crNod->fiu[ !valBit ] == NULL ){
        valBit = !valBit ;
    }

    return findPairInTrie( crNod->fiu [ !valBit ] , crNumIndex , crBit - 1 );
}




int main(){
    int i ;

    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);

    scanf("%d",&noNumbers);

    for ( i = 0 ; i < noNumbers ; i++ ){
        scanf("%d",&valXor [ i ]);
    }

    root = new nodTrie ;
    for ( i = 0 ; i < noNumbers ; i++ ){
        if ( i )
            valXor [ i ] ^= valXor [ i - 1 ] ;

        addValToTrie ( root , i  , FIRSTBIT );

    }

    int maxXorVal = -1  , startSecv , stopSecv , crXorVal , crStart , crStop ;

    for ( i = 0 ; i < noNumbers ; i++ ){
        int j = findPairInTrie( root , i , FIRSTBIT );

        crXorVal = valXor [ i ] ^ valXor [ j ] ;
        crStart = min( i , j ) + 1;
        crStop = max ( i , j );

        if ( crXorVal > maxXorVal ){
            maxXorVal = crXorVal ;
            startSecv = crStart ;
            stopSecv = crStop ;
        }else if ( crXorVal == maxXorVal ){
            if ( crStop < stopSecv ){
                maxXorVal = crXorVal ;
                startSecv = crStart ;
                stopSecv = crStop ;
            }else if ( crStop == stopSecv && crStop - crStart < stopSecv - startSecv ){
                maxXorVal = crXorVal ;
                startSecv = crStart ;
                stopSecv = crStop ;
            }
        }


    }

    printf("%d %d %d",maxXorVal , startSecv + 1 , stopSecv + 1 );

    return 0;
}