Cod sursa(job #948351)

Utilizator misinoonisim necula misino Data 9 mai 2013 23:36:02
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<fstream>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int i,n,x,sol,pi,pf,a[100100];;
struct trie{
    int poz;
    trie *zero,*unu;
    trie()
    {
        zero=unu=NULL;
        poz=0;
    }
};
trie *t=new trie;
void insereaza(trie *t,int p,int x)
{
    if(p<0)
    {
        t->poz=i;
        return ;
    }
    if(x&(1<<p))
    {
        if(!(t->unu))
        {
            t->unu=new trie;
            insereaza(t->unu,p-1,x);
        }
        else
        {
            insereaza(t->unu,p-1,x);
        }
    }
    else
    {
        if(!(t->zero))
        {
            t->zero=new trie;
            insereaza(t->zero,p-1,x);
        }
        else
        {
            insereaza(t->zero,p-1,x);
        }
    }
}

void actualizeaza_solutia(trie *t,int p,int x)
{
    if(p<0)
    {
        if(sol<(a[t->poz]^a[i]))
        {
            sol=a[t->poz]^a[i];
            pi=t->poz+1;
            pf=i;
        }
        return ;
    }
    if(x&(1<<p))
    {
        if(!(t->zero))
        actualizeaza_solutia(t->unu,p-1,x);
        else
        actualizeaza_solutia(t->zero,p-1,x);
    }
    else
    {
        if(!t->unu)
        actualizeaza_solutia(t->zero,p-1,x);
        else
        actualizeaza_solutia(t->unu,p-1,x);
    }
}
int main()
{
    f>>n;
    sol=-1;
    insereaza(t,21,0);
    for(i=1;i<=n;++i)
    {
        f>>x;
        a[i]=a[i-1]^x;
        actualizeaza_solutia(t,21,a[i]);
        insereaza(t,21,a[i]);
    }
    g<<sol<<' '<<pi<<' '<<pf<<'\n';
    return 0;
}