Cod sursa(job #1829519)

Utilizator tqmiSzasz Tamas tqmi Data 15 decembrie 2016 09:11:24
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define Nmax 100005
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct trie
{
    int val,index;
    trie *son[2];
    trie()
    {
        val=0;
        memset(son,0,sizeof(son));
    }
};
trie *T=new trie;
int N,a[Nmax],sol,sole,sols;
void add(int x,trie *nod,int lvl,int ind)
{
    if(lvl==-1)
    {
        nod->val=x;
        nod->index=ind;
        return;
    }
    if(x & (1<<lvl))
    {
        if(nod->son[1]==0)
            nod->son[1]=new trie;
        add(x,nod->son[1],--lvl,ind);
    }
    else
    {
        if(nod->son[0]==0)
            nod->son[0]=new trie;
        add(x,nod->son[0],--lvl,ind);
    }
}

trie* Find(int x,trie *nod,int lvl)
{
    if(lvl==-1)
    {
        return nod;
    }
    if(x & (1<<lvl))
    {
        if(nod->son[0]!=0)
        {
            return Find(x,nod->son[0],--lvl);
        }
        else
        {
            return Find(x,nod->son[1],--lvl);
        }
    }
    else
    {
        if(nod->son[1]!=0)
        {
            return Find(x,nod->son[1],--lvl);
        }
        else
        {
            return Find(x,nod->son[0],--lvl);
        }
    }
}

void read()
{
    fin>>N;
    add(0,T,20,0);
    for(int i=1;i<=N;i++)
    {
        fin>>a[i];
        a[i]^=a[i-1];
        add(a[i],T,20,i);
        trie *b=Find(a[i],T,20);
        if((a[i]^(b->val))>sol)
        {
            if(sole==i )
            {
                sols=max(sols,(b->index)+1);
            }
            else
            {
                sol=(a[i]^(b->val));
                sole=i;
                sols=(b->index)+1;
            }
        }
    }
}

void print()
{
    fout<<sol<<" "<<sols<<" "<<sole<<"\n";
}

int main()
{
    read();
    print();
    return 0;
}