Pagini recente » Cod sursa (job #1569345) | Cod sursa (job #2333568) | Cod sursa (job #1549765) | Statistici Meder Eduart (eduart77) | Cod sursa (job #1998374)
#include <bits/stdc++.h>
using namespace std;
struct trie
{
trie *bt[2];
int sf;
trie ()
{
memset( bt, 0, sizeof(bt) );
}
};
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
int n, i, x, v[100005], ma, a, b, mama, ama, bma;
void add ( trie *&nod, int bit, int nr )
{
if ( bit == 0 )
{
nod->sf = i;
return;
}
if ( nr & bit )
{
if ( nod->bt[1] == 0 )
nod->bt[1] = new trie;
add ( nod->bt[1] , bit/2, nr );
}
else
{
if ( nod->bt[0] == 0 )
{
nod->bt[0] = new trie;
}
add( nod->bt[0] , bit/2, nr );
}
}
int findmax ( trie *&nod, int bit, int nr )
{
if ( bit ==0 )
{
a = nod->sf;
return 0;
}
if ( ( nr & bit ) )
{
if ( nod->bt[0] != 0 )
{
return bit + findmax ( nod->bt[0] , bit/2 , nr );
}
else
{
return findmax ( nod->bt[1] , bit/2 , nr );
}
}
else
{
if ( nod->bt[1] != 0 )
{
return bit + findmax ( nod->bt[1] , bit/2 , nr );
}
else
{
return findmax ( nod->bt[0] , bit/2 , nr );
}
}
}
int main ()
{
fin>>n;
trie *t = new trie;
add( t , 1<<21 , v[i] );
for ( i = 1; i <= n; i++ )
{
fin>>v[i];
v[i] ^= v[i-1];
ma = findmax( t , 1<<21, v[i] );
b=i;
if ( a > b )
{
swap (a, b);
}
a++;
if ( ma > mama )
{
mama = ma;
ama = a;
bma = b;
}
else if ( ma == mama )
{
if ( b < bma )
{
bma = b;
ama = a;
}
else if ( b == bma )
{
if ( a > ama )
{
ama = a;
}
}
}
add( t , 1<<21 , v[i] );
}
fout<< mama << " " << ama << " " << bma;
return 0;
}