Cod sursa(job #1998370)

Utilizator Victor24Vasiesiu Victor Victor24 Data 7 iulie 2017 16:32:08
Problema Xor Max Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <bits/stdc++.h>

using namespace std;

struct trie
{
    trie *bt[2];
    int sf;

    trie ()
    {
        memset( bt, 0, sizeof(bt) );
    }

};

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

int n, i, x, v[100005], ma, a, b, mama, ama, bma;

void add ( trie *&nod, int bit, int nr )
{
    if ( bit == 0 )
    {
        nod->sf = i;
        return;
    }

    if ( nr & bit )
    {
        if ( nod->bt[1] == 0 )
            nod->bt[1] = new trie;
        add ( nod->bt[1] , bit/2, nr );
    }

    else
    {
        if ( nod->bt[0] == 0 )
        {
            nod->bt[0] = new trie;
        }
        add( nod->bt[0] , bit/2, nr );
    }

}

int findmax ( trie *&nod, int bit, int nr )
{

    if ( bit ==0 )
    {
        a = nod->sf;
        return 0;
    }

    if ( ( nr & bit ) )
    {
        if ( nod->bt[0] != 0 )
        {
            return bit + findmax ( nod->bt[0] , bit/2 , nr );
        }
        else
        {
            return findmax ( nod->bt[1] , bit/2 , nr );
        }
    }
    else
    {

        if ( nod->bt[1] != 0 )
        {
            return bit + findmax ( nod->bt[1] , bit/2 , nr );
        }
        else
        {
            return findmax ( nod->bt[0] , bit/2 , nr );
        }
    }

}

int main ()
{
    fin>>n;

    trie *t = new trie;

    add( t , 1<<30 , v[i] );

    for ( i = 1; i <= n; i++ )
    {
        fin>>v[i];
        v[i] ^= v[i-1];
        add( t , 1<<30 , v[i] );
    }

    for ( i = 1 ; i <= n ; i++ )
    {
        ma = findmax( t , 1<<30 , v[i] );
        b=i;
        if ( a > b )
        {
            swap (a, b);
        }
        a++;

        if ( ma > mama )
        {
            mama = ma;
            ama = a;
            bma = b;
        }
        else if ( ma == mama )
        {
            if ( b < bma )
            {
                bma = b;
                ama = a;
            }
            else if ( b == bma )
            {
                if ( a > ama )
                {
                    ama = a;
                }
            }
        }

    }

    fout<< mama << " " << ama << " " << bma;

    return 0;
}