Pagini recente » Cod sursa (job #2243458) | Monitorul de evaluare | Cod sursa (job #175586) | Cod sursa (job #3273744) | Cod sursa (job #2047564)
#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 = 1 ; i < noNumbers ; 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;
}