Cod sursa(job #1953522)

Utilizator robertpop99Popescu Robert Gabriel robertpop99 Data 4 aprilie 2017 21:11:54
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>
using namespace std;
int s[100005],n,x,sol=-1,maxi=1,maxj=1;

struct trie
{
    int ind;
    trie *son[2];
    trie()
    {
        ind=0;
        son[1]=son[0]=NULL;
    }
};

trie *root = new trie();

void inser(trie *nod, int s, int ind, int poz=21)
{
    if(poz==-1)
    {
        nod->ind = ind;
        return;
    }

    int bit=(s>>poz)&1;
    if(nod->son[bit]==NULL)
        nod->son[bit]=new trie();
    inser(nod->son[bit],s,ind,poz-1);
}

int query(trie *nod, int s, int poz=21)
{
    if(poz==-1)
    {
        return nod->ind;
    }
    int bit=(s>>poz)&1;
    if(nod->son[1-bit]!=NULL) query(nod->son[1-bit],s,poz-1);
    else query(nod->son[bit],s,poz-1);
}
int main()
{
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    fin>>n;
    inser(root,0,0);
    for(int i=1;i<=n;i++)
    {   fin>>x;
        s[i]=x^s[i-1];
        inser(root,s[i],i);
        int poz=query(root,s[i]);
        if(sol<(s[i]^s[poz]))
        {   sol=s[i]^s[poz];
            maxi=poz+1;
            maxj=i;
        }

    }
    fout<<sol<<' '<<maxi<<' '<<maxj<<'\n';
    return 0;
}