Pagini recente » Cod sursa (job #1099817) | Cod sursa (job #185030) | Cod sursa (job #330698) | Cod sursa (job #631870) | Cod sursa (job #1783159)
# include <iostream>
# include <fstream>
using namespace std;
/// ******************** class node ********************
class node
{
public:
pair<int, int> find( int n, int l );
void push( int n, int l, pair<int, int> val );
private:
node * sub[2];
pair<int, int> val;
};
pair<int, int> node::find( int n, int l )
{
if ( l == 0 )
return val;
if ( sub[n & 1] != NULL )
return sub[n & 1]->find( n >> 1, l - 1 );
else
return sub[n & 1 ^ 1]->find( n >> 1, l - 1 );
}
void node::push( int n, int l, pair<int, int> val )
{
if ( l == 0 )
this->val = val;
else {
if ( sub[n & 1] == NULL )
sub[n & 1] = new node;
sub[n & 1]->push( n >> 1, l - 1, val );
}
}
/// ******************** class xor_trie ********************
class xor_trie
{
public:
xor_trie( void );
void push( int n, int pos );
pair<int, int> find( int n );
private:
node * trie;
int invert( int n );
};
xor_trie::xor_trie( void ) {
trie = new node;
}
int xor_trie::invert( int n ) {
int r = 0;
for ( int i = 0; i < 21; i ++ ) {
r = ( ( r << 1 ) | ( n & 1 ) );
n >>= 1;
}
return r;
}
void xor_trie::push( int n, int pos )
{
int r = invert( n );
trie->push( r, 21, make_pair( n, pos ) );
}
pair<int, int> xor_trie::find( int n )
{
n = invert( n );
return trie->find( n, 21 );
}
# define MASK ( ( 1 << 21 ) - 1 )
int main()
{
ifstream fin( "xormax.in" );
ofstream fout( "xormax.out" );
int n, i, nr, s, m_val, m_st, m_dr;
xor_trie table;
pair<int, int> z;
fin >> n;
table.push( s = 0, 0 );
m_val = -1;
for ( i = 1; i <= n; i ++ ) {
fin >> nr;
s ^= nr;
z = table.find( s ^ MASK );
if ( ( z.first ^ s ) > m_val ) {
m_val = ( z.first ^ s );
m_st = z.second + 1;
m_dr = i;
}
table.push( s, i );
}
fout << m_val << ' ' << m_st << ' ' << m_dr;
fin.close();
fout.close();
return 0;
}