Cod sursa(job #788869)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 15 septembrie 2012 23:30:40
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 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=0;
int SANS,FANS=100010;

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

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

    if (!T->Son[v])
        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);
    if (v) v=1;

    if (T->Son[!v])
    {
        if (!v) Y|=1<<p;
        Search(T->Son[!v],V,p);
    }
    else
    {
        if (v) Y|=1<<p;
        Search(T->Son[v],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;
}