Cod sursa(job #3170082)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 16 noiembrie 2023 19:44:29
Problema Xor Max Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>

using namespace std;
int n,k,x,y,p,poz,val,bit,maxi,st,dr;
struct trie
{
    int ind,pz,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].pz=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;
            st=w[poz].pz;
            dr=i;
        }
        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;
                w[k].pz=i;
                poz=k;
            }
            p/=2;
        }
    }
    g<<maxi<<" "<<st+1<<" "<<dr;
    return 0;
}