Cod sursa(job #1224116)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 29 august 2014 19:14:56
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <cstring>
#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=-1;
struct Trie{
Trie* next[2];
    Trie()
    {
        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;
    }
    Bit[0]=22;
}

void Browse(int poz)
{
    Trie *node=Root;
    int number=0;
    for(int i=Bit[0];i>=1;i--)
    {
        if(node->next[1-Bit[i]]!=0)
        {
            number=number*2+1;
            node=node->next[1-Bit[i]];
        }
        else
        {
            number=number*2;
            node=node->next[Bit[i]];
        }
    }
    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);
}
void getAnswer()
{
    int i,number=Array[1];
    Max=Array[1];
    stop=1;
    Descomp(Array[1]);
    insert(Root,Bit[0]);
    memset(Bit,0,sizeof(Bit));
    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]);
        memset(Bit,0,sizeof(Bit));
    }
}
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;
}