Cod sursa(job #3170078)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 16 noiembrie 2023 19:42:00
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>

using namespace std;
int n,k,x,y,p,poz,val,bit,maxi;
struct trie
{
    int ind,cp[2];
}w[1<<21];
int main()
{
    ifstream f("xormax.in");
    ofstream g("xormax.out");
    f>>n;
    for(int i=1; i<=21; i++)
    {
        k++;
        w[k].ind=0;
        w[k].cp[0]=k+1;
    }
    w[k].cp[0]=0;//am adaugat 0 in trie
    for(int i=1; i<=n; i++)
    {
        f>>x;
        x=x^y;
        y=x;
        p=1<<20;
        poz=0;
        while(p>=1)
        {
            bit=(x/p)%2;
            //g<<bit;
            if(w[poz].cp[1-bit]) poz=w[poz].cp[1-bit];
            else poz=w[poz].cp[bit];
            p/=2;
        }
        //g<<'\n';
        //g<<x<<" "<<w[poz].ind<<'\n';
        val=x^w[poz].ind;
        if(val>maxi) maxi=val;
        p=1<<20;
        poz=0;
        val=0;
        while(p>=1)
        {
            bit=(x/p)%2;
            val*=2;
            val+=bit;
            if(w[poz].cp[bit]) poz=w[poz].cp[bit];
            else
            {
                w[poz].cp[bit]=k+1;
                k++;
                w[k].ind=val;
                poz=k;
            }
            p/=2;
        }
    }
    g<<maxi;
    return 0;
}