Pagini recente » Cod sursa (job #3198396) | Rating Burla Codrin Alexandru (bcodrin) | Cod sursa (job #273087) | Cod sursa (job #2735530) | Cod sursa (job #2047576)
#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 ;
}
}
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;
}