Cod sursa(job #1725213)

Utilizator felixiPuscasu Felix felixi Data 5 iulie 2016 10:54:32
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream in( "xormax.in" );
ofstream out( "xormax.out" );

const int NMAX  = 100000;
const int SIGMA = 2;

struct Trie {
    int id, nrf;
    Trie *fiu[SIGMA];

    Trie() {
        id = nrf = 0;
        for( int i = 0;  i < SIGMA;  ++i ) {
            fiu[i] = NULL;
        }
    }
};

Trie *Trie_Root = new Trie;

///   #Trie
int CH( char ch ) {
    return ( (int)(ch - '0') );
}

void Insert( Trie *nod, int key, int poz, int cat = 22 ) {
    if( cat < 0 ) {
        nod->id = poz;
        return ;
    }
    int ff = ( (key & (1 << cat)) != 0 );
    if( nod->fiu[ ff ] == NULL ) {
        nod->fiu[ ff ] = new Trie;
        nod->nrf++;
    }
    Insert( nod->fiu[ ff ] , key, poz, cat - 1 );
}

int Query( Trie *nod, int key, int cat = 22 ) {
    if( cat < 0 ) {
        return nod->id;
    }
    int ff = 1 - ((key & (1 << cat)) != 0);
    if( nod->fiu[ ff ] ) {
        return ( Query( nod->fiu[ ff ] , key, cat - 1 ) );
    }
    return Query( nod->fiu[ 1-ff ], key, cat - 1 ) ;
}

int N, v[NMAX+2], Ans = -1, st, dr;

int main() {
    Trie *RootTrie = new Trie;
    Insert( RootTrie, 0, 0 );

    in >> N;
    for( int i = 1;  i <= N;  ++i ) {
        in >> v[i];
        v[i] ^= v[i-1];
        int capat = Query( RootTrie, v[i] );
        if( ( v[i] ^ v[capat] ) > Ans ) {
            Ans = v[i] ^ v[capat];
            st = capat + 1;
            dr = i;
        }
        Insert( RootTrie, v[i], i );
    }
    out << Ans << ' ' << st << ' ' << dr << '\n';

    return 0;
}