Cod sursa(job #601690)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 iulie 2011 14:14:24
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <fstream>

#define NMax 100005

using namespace std;

struct Trie
{
    int NS;
    Trie *Son[2];
    Trie ()
    {
        NS=-1;
        Son[0]=Son[1]=0;
    }
};

Trie *T=new Trie;
int N, X[NMax], XorMax[NMax], Start, End, S;

void Read ()
{
    ifstream fin ("xormax.in");
    fin >> N;
    for (int i=1; i<=N; ++i)
    {
        fin >> X[i];
    }
    fin.close ();
}

void Print ()
{
    ofstream fout ("xormax.out");
    fout << S << " " << Start << " " << End << "\n";
    fout.close ();
}

void Insert (Trie *Node, int Element, int Bit)
{
    if (Bit==-1)
    {
        Node -> NS=Element;
        return;
    }
    if (((1<<Bit)&Element)!=0)
    {
        if (Node -> Son[1]==0)
        {
            Node -> Son[1]=new Trie;
        }
        Insert (Node -> Son[1], Element, Bit-1);
    }
    else
    {
        if (Node -> Son[0]==0)
        {
            Node -> Son[0]=new Trie;
        }
        Insert (Node -> Son[0], Element, Bit-1);
    }
}

int Query (Trie *Node, int Q, int Bit)
{
    if (Bit==-1)
    {
        return Node-> NS;
    }
    if ((Q&(1<<Bit))!=0)
    {
        if (Node -> Son[0]!=0)
        {
            return Query (Node -> Son[0], Q, Bit-1);
        }
        return Query (Node -> Son[1], Q, Bit-1);
    }
    if (Node -> Son[1]!=0)
    {
        return Query (Node -> Son[1], Q, Bit-1);
    }
    return Query (Node -> Son[0], Q, Bit-1);
}

int main()
{
    int Xor, CurrentXor;
    Read ();
    XorMax[1]=X[1];
    CurrentXor=X[1];
    Insert (T, X[1], 21);
    Start=1;
    End=1;
    S=XorMax[1];
    for (int i=2; i<=N; ++i)
    {
        CurrentXor^=X[i];
        Xor=Query (T, CurrentXor, 21);
        XorMax[i]=max (X[i], CurrentXor^Xor);
        Insert (T, CurrentXor, 21);
        if (XorMax[i]>S)
        {
            S=XorMax[i];
            End=i;
        }
    }
    Xor=X[End];
    Start=End;
    for (int i=End-1; i>0 && Xor!=S; --i)
    {
        Xor^=X[i];
        Start=i;
    }
    Print ();
    return 0;
}