Cod sursa(job #997635)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 14 septembrie 2013 17:40:44
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>

using namespace std;

const int Nmax = 100005;

struct Trie
{
    int indice;
    Trie *son[2];

    Trie()
    {
        son[0] = 0;
        son[1] = 0;
        indice = 0;
    }
};

Trie *T = new Trie;

int N;
int X[Nmax];
string sir;
int maxim = -INT_MAX, stanga, dreapta;

void read()
{
    ifstream f("xormax.in");

    f >> N;

    getline( f, sir );
    getline( f, sir );

    unsigned l = sir.size();
    int index = 0, nr = 0;

    for ( unsigned i = 0; i <= l; ++i )
            if ( isdigit( sir[i] ) )
                nr = nr * 10 + ( sir[i] - 48 );
            else
            {
                X[ ++index ] = nr ^ X[index - 1];
                nr = 0;
            }

    f.close();
}

void insereaza( Trie *nod, int sum, int exp, int index )
{
    if ( exp == -1 )
    {
        nod->indice = index;
        return;
    }

    bool bit = ( sum & ( 1 << exp ) );

    if ( nod->son[bit] == 0 )
            nod->son[bit] = new Trie;

    insereaza( nod->son[bit], sum, exp - 1, index );
}

void query( int sum, int finish )
{
    Trie *nod = T;

    for ( int i = 21; i >= 0; i-- )
    {
        bool bit = sum & ( 1 << i );

        if ( nod->son[bit ^ 1] )
                nod = nod->son[bit ^ 1];
        else
                nod = nod->son[bit];
    }

    if ( sum ^ X[nod->indice] > maxim )
    {
        maxim = sum ^ X[nod->indice];
        stanga = nod->indice + 1;
        dreapta = finish;
    }
}

void solve()
{
    insereaza( T, 0, 21, 0 );

    for ( int i = 1; i <= N; ++i )
    {
        insereaza( T, X[i], 21, i );
    }

    for ( int i = 1; i <= N; ++i )
    {
        query( X[i], i );
    }
}

void print()
{
    ofstream g("xormax.out");

    g << maxim << " " << stanga << " " << dreapta << "\n";

    g.close();
}

int main()
{
    read();
    solve();
    print();

    return 0;
}