Cod sursa(job #2047581)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 24 octombrie 2017 23:52:34
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 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 ;

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


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

            int j = findPairInTrie( root , i , FIRSTBIT );

            crXorVal = valXor [ i ] ^ valXor [ j ] ;
            crStart = j + 1;
            crStop = i;

            if ( crXorVal > maxXorVal ){
                maxXorVal = crXorVal ;
                startSecv = crStart ;
                stopSecv = crStop ;
            }

        }else{
            maxXorVal = valXor [ 0 ] ;
            startSecv = 0 ;
            stopSecv = 0 ;
        }


        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;
}