Cod sursa(job #3187318)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 28 decembrie 2023 14:14:13
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct trie{

    struct nod{
        nod* ch[2]={NULL,NULL};
        int ind=0;
    }root;

    void insert(int val,int ind)
    {
        nod* a = &root;
        for(int i = 21;i>=0;i--)
        {
            if(!a->ch[(val>>i)&1])
                a->ch[(val>>i)&1] = new nod;
            a=a->ch[(val>>i)&1];
        }
        a->ind=ind;
    }
    pair<int,int> query(int val)
    {
        nod* a= &root;
        int value=0;
        for(int i=21;i>=0;i--)
        {
            int inv = 1-((val>>i)&1);
            if(a->ch[inv])
                a=a->ch[inv],value+=((1<<i)*inv);
            else
                a=a->ch[1-inv],value+=((1<<i)*(1-inv));

        }
        return pair<int,int>{value,a->ind};
    }


}t;

int n;
int lx;

int solmax;
int solst;
int soldr;

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        fin>>x;
        lx^=x;
        if( x > solmax)
            solmax=x,solst=i,soldr=i;

        if(i!=1)
        {
            pair<int,int> s = t.query(lx);
            s.first^=lx;
            if(s.first > solmax)
                solmax=s.first,solst=s.second,soldr=i;
        }
        t.insert(lx,i+1);
    }
    fout<<solmax<<' '<<solst<<' '<<soldr;
}