Cod sursa(job #2740288)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 12 aprilie 2021 14:32:44
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
typedef long long ll;
int n,s[200005],l,r;
struct node
{
    int bestpoz;
    int muchii[2];
};
node emptynode;
vector<node> t;
ll ans;
const int inf=1e9;
void addnum(int nr, int index)
{
    int v=0;
    for(int bit=20;bit>=0;bit--)
    {
        int val=((nr>>bit)&1);
        if(t[v].muchii[val]==-1)
        {
            node x=emptynode;
            x.bestpoz=index;
            t[v].muchii[val]=t.size();
            t.push_back(x);
        }
        v=t[v].muchii[val];
        t[v].bestpoz=index;
    }
}
int go(int nod,int val)
{
    return t[nod].muchii[val];
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        fin>>x;
        s[i]=(s[i-1]^x);
    }
    /*if(n==1)
    {
        fout<<s[1]<<" 1 1";
        return 0;
    }*/
    //fout<<query(1,0,(1<<21),3,120)<<'\n';
    emptynode.muchii[0]=-1;
    emptynode.muchii[1]=-1;
    t.push_back(emptynode);
    addnum(s[0],0);
    for(int i=1;i<=n;i++)
    {
        int nr=0;
        int v=0;
        for(int bit=20;bit>=0;bit--)
        {
            if((s[i]>>bit)&1)
            {
                int bestpoz=t[go(v,0)].bestpoz;
                if(bestpoz!=-1)
                {
                    int val=(s[i]^s[bestpoz]);
                    if(val>ans)
                    {
                        ans=val;
                        l=bestpoz+1;
                        r=i;
                    }
                    v=go(v,0);
                }
                else
                {
                    nr+=(1<<bit);
                    v=go(v,1);
                }
            }
            else
            {
                int bestpoz=t[go(v,1)].bestpoz;
                if(bestpoz!=-1)
                {
                    int val=(s[i]^s[bestpoz]);
                    if(val>ans)
                    {
                        ans=val;
                        l=bestpoz+1;
                        r=i;
                    }
                    v=go(v,1);
                    nr+=(1<<bit);
                }
                else
                    v=go(v,0);
            }
        }
        addnum(s[i],i);
    }
    if(l==0&&r==0)
    {
        fout<<s[1]<<" "<<1<<" "<<1;
        return 0;
    }
    fout<<ans<<" "<<l<<" "<<r;
    return 0;
}