Cod sursa(job #2049564)

Utilizator cameleonGeorgescu Dan cameleon Data 27 octombrie 2017 13:11:37
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct trie
{
    trie *next[2];
    int val;
}*d,*p;

int n,x[100005],val,in,Max=0,init,fi;


void mx(int val,int &sum,int &poz)
{
    sum=0;
    poz=0;
    for(int i=21;i>=0;i--)
    {
        bool bit=(((1<<i)&val)!=0);
        bool bit1=bit;
        if(p->next[1-bit]!=0)
            bit1=1-bit;
        sum=sum*2+(bit^bit1);
        poz=poz*2+bit1;
        p=p->next[bit1];
    }
}

void adauga(int val,int act)
{
    for(int i=21;i>=0;i--)
    {
        bool bit=(((1<<i)&val)!=0);
        if(p->next[bit]==0)
        {
            trie *s=new trie;
            s->next[0]=0;
            s->next[1]=0;
            p->next[bit]=s;
            p=s;
            p->val=act+1;
        }
        else
        {
            p=p->next[bit];
            p->val=act+1;
        }
    }
}


int main()
{
    fin>>n;
    d=new trie;
    d->next[0]=0;
    d->next[1]=0;
    p=d;
    for(int i=0;i<=21;i++)
    {
        trie *s=new trie;
        s->next[0]=0;
        s->next[1]=0;
        p->next[0]=s;
        p=s;
        p->val=1;
    }
    int vi;
    for(int i=1;i<=n;i++)
    {
        fin>>x[i];
        p=d;
        x[i]=x[i-1]^x[i];
        mx(x[i],val,in);
        if(Max<val)
        {
            Max=val;
            vi=in;
            fi=i;
        }
        p=d;
        adauga(x[i],i);

    }
   for(int i=1;i<fi;i++)
   if(vi==x[i]){
    init=i+1;
   }
    fout<<Max<<" "<<init<<" "<<fi;
    return 0;
}