Cod sursa(job #3163878)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 1 noiembrie 2023 14:53:59
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
using namespace std;
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
int st,dr,n,val,maxim,x,i;
struct el
{
    int x,poz;
};
el l;
struct trie
{
    trie *next[2];
    int val,poz;
    trie ()
    {
        next[0]=next[1]=NULL;
        val=poz=0;
    }
};
trie *p;
void add (trie *nod,int val,int pozi)
{
    for (int p=20; p>=0; p--)
    {
        int bit=(val>>p)&1;
        if (nod->next[bit]==NULL)
            nod->next[bit]=new trie;
        nod=nod->next[bit];
    }
    nod->val=val;
    nod->poz=pozi;
}
el query (trie *nod,int val)
{
    for (int p=20; p>=0; p--)
    {
        int bit=(val>>p)&1;
        if (nod->next[1-bit]!=NULL)
            nod=nod->next[1-bit];
        else
            nod=nod->next[bit];
    }
    return {nod->val,nod->poz};
}
int main()
{
    p=new trie;
    fin>>n;
    add (p,0,0);
    for (i=1; i<=n; i++)
    {
        fin>>x;
        val^=x;
        add (p,val,i);
        l=query (p,val);
        if (val^(l.x)>maxim)
        {
            maxim=val^(l.x);
            st=l.poz+1;
            dr=i;
        }
    }
    fout<<maxim<<" "<<st<<" "<<dr;
    return 0;
}