Pagini recente » Cod sursa (job #437745) | Cod sursa (job #1245289) | Cod sursa (job #1565150) | Cod sursa (job #2079963) | Cod sursa (job #2015978)
#include<fstream>
#include<cmath>
#define DIM 100000
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int s[DIM], n, P, S, sol, st, dr, E;
struct trie{
int poz;
trie *next[2];
trie(){
this->poz = 0;
this->next[0] = this->next[1] = NULL;
}
};
trie *rad;
void Insert( trie *nod, int x, int p, int i ){
if( p == -1 ){
nod->poz = max( nod->poz, i );
}else{
int bit = ( (x>>p) & 1 );
if( nod->next[bit] == NULL ){
nod->next[bit] = new trie();
}
Insert( nod->next[bit], x, p - 1, i );
}
return;
}
void query( trie *nod, int x, int p ){
if( p == -1 ){
P = nod->poz;
}else{
int bit = ( (x>>p) & 1 );
if( nod->next[!bit] == NULL ){
S += (1<<p) * (bit);
query( nod->next[bit], x, p - 1 );
}else{
S += (1<<p) * (!bit);
query( nod->next[!bit], x, p - 1 );
}
}
return;
}
int main(){
fin >> n;
rad = new trie();
for( int i = 1; i <= n; i++ ){
fin >> s[i];
s[i] = s[i] ^ s[i - 1];
if( sol < s[i] ){
sol = s[i];
st = 1;
dr = i;
}
E = max( E, ilogb( s[i] ) );
}
E++;
Insert( rad, 0, E, 0 );
for( int i = 1; i <= n; i++ ){
P = S = 0;
query( rad, s[i], E );
if( sol < (S ^ s[i]) ){
sol = (S ^ s[i]);
st = P + 1;
dr = i;
}
Insert( rad, s[i], E, i );
}
fout << sol << " " << st << " " << dr;
return 0;
}