Cod sursa(job #2049623)

Utilizator cameleonGeorgescu Dan cameleon Data 27 octombrie 2017 15:05:57
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>

using namespace std;

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

struct trie
{
    trie *next[2];
    int val;
    trie(){
        next[0]=next[1]=0;
        val=1;
    }
}*d,*p;

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

void mx(int val,int &sum,int &poz)
{
    sum=0;
    poz=0;
    p=d;
    for(int i=22;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)
{
    p=d;
    for(int i=22;i>=0;i--)
    {
        bool bit=(((1<<i)&val)!=0);
        if(p->next[bit]==0)
        {
            trie *s=new trie;
            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;
    p=d;
    for(int i=0;i<=22;i++)
    {
        trie *s=new trie;
        p->next[0]=s;
        p=s;
        p->val=1;
    }
    int vi=0;
    for(int i=1;i<=n;i++)
    {
        fin>>x[i];
        x[i]=x[i-1]^x[i];
        mx(x[i],val,in);
        if(Max<val)
        {
            Max=val;
            vi=in;
            fi=i;
        }
        adauga(x[i],i);

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