Cod sursa(job #1245706)

Utilizator xtreme77Patrick Sava xtreme77 Data 19 octombrie 2014 21:00:17
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <vector>
#include <cstring>

#define pb push_back

const char IN [ ] = "xormax.in" ;
const char OUT [ ] = "xormax.out" ;
const int MAX = 100014 ;

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

int v [ MAX ] , sp [ MAX ] , sol , index ;
bool bin [ 24 ] ;

struct TRIE {
    int nxt [ 2 ] ;
    TRIE ( )
    {
        nxt [ 0 ] = nxt [ 1 ] = -1 ;
    }
};

TRIE GOL ;

vector < TRIE > d ;

void build ( int val )
{
    memset ( bin , 0 , sizeof ( bin ) ) ;
    int poz = 21 ;
    while ( val )
    {
        bin [ poz -- ] = val & 1 ;
        val >>= 1 ;
    }
}

void add ( int nod , int pos )
{
    if ( pos == 22 )
        return ;
    int next = d [ nod ].nxt [ bin [ pos ] ] ;
    if ( next == -1 )
    {
        int ret = d.size ( ) ;
        d.pb ( GOL ) ;
        next = d [ nod ].nxt [ bin [ pos ] ] = ret ;
    }
    add ( next , pos + 1 ) ;
}

int QQ ( int nod , int pos )
{
    if ( pos == 22 )
        return 0 ;
    int caut = 1 - bin [ pos ] ;
    for ( int i = 0 ; i <= 1 ; ++ i )
    {
        if ( d [ nod ].nxt [ caut ] != -1 )
            return ( 1 << ( 21 - pos ) ) * caut + QQ ( d [ nod ].nxt [ caut ] , pos + 1 ) ;
        caut = 1 - caut ;
    }
}

int main(              )
{
    int n ;
    fin >> n ;
    for ( int i = 1 ; i <= n ; ++ i )
    {
        fin >> v [ i ] ;
        sp [ i ] = sp [ i - 1 ] ^ v [ i ] ;
    }
    d.pb ( GOL ) ;
    add ( 0 , 1 ) ;
    for ( int i = 1 ; i <= n ; ++ i )
    {
        build ( sp [ i ] ) ;
        int cur = QQ ( 0 , 1 ) ;
        cur ^= sp [ i ] ;
        if ( cur > sol )
        {
            sol = cur ;
            index = i ;
        }
        add ( 0 , 1 ) ;
    }
    fout << sol << ' ' ;
    for ( int i = index ; i >= 1 ; -- i )
        if ( ( sp [ index ] ^ sp [ i - 1 ] ) == sol )
        {
            fout << i << ' ' << index << '\n' ;
            return 0 ;
        }
    return 0;
}