Cod sursa(job #788880)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 15 septembrie 2012 23:45:47
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>

using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

struct Trie
{
    int P;
    Trie *Son[2];
    Trie ()
    {
        P=0;
        Son[0]=Son[1]=0;
    }
} *T=new Trie();

int N,i;
int X,S,Y,P;
int ANS=-1;
int SANS,FANS=0;

void Insert (Trie *T, int V, int p)
{
    if (p==0)
    {
        T->P=P;
        return;
    }

    p--;
    int v=(V&(1<<p))>0;

    if (T->Son[v]==0)
        T->Son[v]=new Trie();

    Insert(T->Son[v],V,p);
}

void Search (Trie *T, int V, int p)
{
    if (p==0)
    {
        P=T->P;
        return;
    }

    p--;
    int v=(V&(1<<p))>0;

    if (v==1)
    {
        if (T->Son[0])
            Search(T->Son[0],V,p);
        else
        {
            Y|=1<<p;
            Search(T->Son[1],V,p);
        }
    }
    else
    {
        if (T->Son[1])
        {
            Y|=1<<p;
            Search(T->Son[1],V,p);
        }
        else
            Search(T->Son[0],V,p);
    }
}

int main ()
{
    f >> N;
    P=0;
    Insert(T,0,21);
    for (i=1; i<=N; i++)
    {
        f >> X;
        S^=X;
        Y=0;
        P=0;
        Search(T,S,21);
        if ((S^Y)>ANS || ((S^Y)==ANS && FANS-SANS>i-P))
        {
            ANS=S^Y;
            SANS=P;
            FANS=i;
        }
        P=i;
        Insert(T,S,21);
    }

    g << ANS << ' ' << SANS+1 << ' ' << FANS << '\n';

    f.close();
    g.close();
    return 0;
}