Cod sursa(job #1223316)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 27 august 2014 11:31:04
Problema Xor Max Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int N,Array[NMAX];
int Bit[25];
int start,stop,Max;
struct Trie{
int aparition,position,diam;
Trie* next[2];
    Trie()
    {
        aparition=position=diam=0;
        next[0]=next[1]=0;
    }
};
Trie* Root=new Trie;
void Read()
{
    int i;
    f>>N;
    for(i=1;i<=N;i++)
        f>>Array[i];
}

void Descomp(int x)
{
    Bit[0]=0;
    while(x!=0)
    {
        Bit[++Bit[0]]=x%2;
        x/=2;
    }
}

void Browse(int poz)
{
    int index=Bit[0],number=0;
    Trie* node=(Root->next[1]);
    if(Root->diam<=Bit[0])
    {
        index=Root->diam;
        node=Root;
        int ind=Bit[0];
        while(ind>index)
        {
            number=number*2+Bit[ind];
            --ind;
        }
    }
    else
    {
        node=Root;
        int value=1;
        while(node!=0 && node->diam>Bit[0])
        {
            if((node->next[1])!=0 && (node->next[1])->diam==node->diam-1)
            {
                node=node->next[1];
                value=1;
            }
            else
            {
                node=node->next[0];
                value=0;
            }
            number=number*2+value;
        }
    }
    while(index>0)
    {
        if(node->next[1-Bit[index]]!=0 && (node->next[1-Bit[index]])->diam==node->diam-1)
        {
            node=node->next[1-Bit[index]];
            number=number*2+1;
        }
        else
        {
            node=node->next[Bit[index]];
            number=number*2;
        }
        --index;
    }
    if(number>Max)
    {
        Max=number;
        stop=poz;
    }
}

void insert(Trie* node,int poz)
{
    if(poz==0)
        return;
    if(node->next[Bit[poz]]==0)
        node->next[Bit[poz]]=new Trie;
    insert(node->next[Bit[poz]],poz-1);
    node->diam=max(node->diam,(node->next[Bit[poz]])->diam+1);
}
void getAnswer()
{
    int i,number=Array[1];
    Max=Array[1];
    stop=1;
    Descomp(Array[1]);
    insert(Root,Bit[0]);
    for(i=2;i<=N;i++)
    {
        number=number^Array[i];
        if(Max<number)
        {
            Max=number;
            stop=i;
        }
        Descomp(number);
        Browse(i);
        insert(Root,Bit[0]);
    }
}
void countBegin()
{
    int i=stop,number=Array[stop];
    while(i>0 && number!=Max)
    {
        i--;
        number=Array[i]^number;
    }
    g<<Max<<" "<<i<<" "<<stop<<"\n";
}
int main()
{
    Read();
    getAnswer();
    countBegin();
    return 0;
}