Cod sursa(job #3135093)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 1 iunie 2023 20:00:10
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
const int dim=1<<17;
char next_ch()
{
    static int bp=dim;
    static char buff[dim];
    if(bp==dim)
    {
        fread(buff,1,dim,stdin);
        bp=0;
    }
    return buff[bp++];
}
void get(int &a)
{
    a=0;
    char ch;
    do
    {
        ch=next_ch();
    }
    while(ch<'0'||'9'<ch);
    do
    {
        a=a*10+ch-'0';
        ch=next_ch();
    }
    while('0'<=ch&&ch<='9');
}
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()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    int n,sor=0,x,i;
    get(n);
    baga(root,0,20,0);
    for(i=1;i<=n;i++)
    {
        get(x);
        sor^=x;
        query(root,sor,20,i,0);
        baga(root,sor,20,i);
    }
    std::cout<<max1<<" "<<l<<" "<<r;
    return 0;
}