Cod sursa(job #997645)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 14 septembrie 2013 17:49:53
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 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 = -1, stanga, dreapta;

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

    f >> N;

    for ( int i = 1; i <= N; ++i )
    {
        f >> X[i];
        X[i] ^= X[i - 1];
    }

    /*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 insereaza( Trie *nod , int sum , int ind, int index) {

    if (ind == -1) {
        nod -> indice = index;
        return;
    }

    bool t = ( sum & (1 << ind));

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

    insereaza (nod -> son[t] , sum , ind - 1, index);

}

void query (int sum , int finish) {

    int i;
    Trie *nod = T;

    for( i = 21 ; i >= 0 ; --i ) {
        bool t = (sum & (1 << i));
        if ( nod -> son[t ^ 1] )
            nod = nod -> son[t ^ 1];
        else
            nod = nod -> son[t];
    }

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

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

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

    for ( int i = 1; i <= N; ++i )
    {

    }
}

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

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

    g.close();
}

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

    return 0;
}