Cod sursa(job #2742538)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 21 aprilie 2021 10:03:38
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <fstream>
#define nl '\n'
using namespace std;
ifstream f ( "xormax.in" );
ofstream g ( "xormax.out" );
const int NMAX = 100001;
int v[NMAX];
struct Trie
{
    Trie *Fiu[2];
    int index;
    Trie()
    {
        index = -1;
        Fiu[1] = Fiu[0] = NULL;
    }
};
void Insert ( Trie *Node, int bit, int index )
{
    if ( bit == 0 )
    {
        Node->index = index;
        return;
    }

    int valbit = ( ( ( 1 << bit ) & v[index] ) != 0 );

    if ( Node->Fiu[valbit] == NULL )
        Node->Fiu[valbit] = new Trie();

    Insert ( Node->Fiu[valbit], bit - 1, index );
}
int Query ( Trie *Node, int bit, int index )
{
    if ( bit == 0 )
        return Node->index;

    int valbit = ( ( ( 1 << bit ) & v[index] ) != 0 );

    if ( Node->Fiu[1 - valbit] != NULL )
        return Query ( Node->Fiu[1 - valbit], bit - 1, index );

    return Query ( Node->Fiu[valbit], bit - 1, index );
}
int main()
{
    Trie *T = new Trie;
    Insert ( T, 20, 0 );
    int N, Vmax = 0, start = 1, stop = 1;
    f >> N;

    for ( int i = 1; i <= N; i++ )
    {
        int nr;
        f >> nr;
        v[i] = ( v[i - 1] ^ nr );
        int poz = Query ( T, 20, i );

        if ( ( v[poz]^v[i] ) > Vmax )
        {
            Vmax = ( v[poz] ^ v[i] );
            stop = i;
            start = poz + 1;
        }

        Insert ( T, 20, i );
    }

    g << Vmax << ' ' << start << ' ' << stop;
    return 0;
}