Cod sursa(job #2917058)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 2 august 2022 21:05:20
Problema Xor Max Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
int max1=-1,l,r;
struct Trie{
    int poz;
    Trie *fiu[2];
    Trie(){
        fiu[0]=fiu[1]=NULL;
    }
};
Trie *root=new Trie;
void baga(Trie *nod,int val,int poz,int upd)
{
    if(poz==-1)
    {
        nod->poz=upd;
        return;
    }
    int next=0;
    if(val&(1<<poz))
        next=1;
    if(nod->fiu[next]==NULL)
    {
        Trie *urm=new Trie;
        nod->fiu[next]=urm;
    }
    baga(nod->fiu[next],val,poz-1,upd);
}
void query(Trie *nod,int val,int poz,int upd,int cat)
{
    if(poz==-1)
    {
        if((cat^val)>max1)
        {
            max1=cat^val;
            l=nod->poz+1;
            r=upd;
        }
        return;
    }
    int next=1;
    if(val&(1<<poz))
        next=0;
    if(nod->fiu[next]==NULL)
        next=1-next;
    query(nod->fiu[next],val,poz-1,upd,cat+(next<<poz));
}
int main()
{
    int n,sor=0,x,i;
    in>>n;
    baga(root,0,20,0);
    for(i=1;i<=n;i++)
    {
        in>>x;
        sor^=x;
        query(root,sor,20,i,0);
        baga(root,sor,20,i);
    }
    out<<max1<<" "<<l<<" "<<r;
    return 0;
}