Cod sursa(job #1783159)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 18 octombrie 2016 20:23:43
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
# 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;
}