Cod sursa(job #2740285)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 12 aprilie 2021 14:17:12
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 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,f[3000005][21];
ll ans;
const int inf=1e9;
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;
    }*/
    for(int i=1;i<=3*1e6;i++)
        memset(f[i],-1,sizeof(f[i]));
    //fout<<query(1,0,(1<<21),3,120)<<'\n';
    for(int i=1;i<=n;i++)
    {
        int nr=0;
        for(int bit=20;bit>=0;bit--)
        {
            if((s[i]>>bit)&1)
            {
                int bestpoz=f[nr][bit];
                if(bestpoz!=-1)
                {
                    int val=(s[i]^s[bestpoz]);
                    if(val>ans)
                    {
                        ans=val;
                        l=bestpoz+1;
                        r=i;
                    }
                }
                else
                    nr+=(1<<bit);
            }
            else
            {
                int bestpoz=f[nr+(1<<bit)][bit];
                if(bestpoz!=-1)
                {
                    int val=(s[i]^s[bestpoz]);
                    if(val>ans)
                    {
                        ans=val;
                        l=bestpoz+1;
                        r=i;
                    }
                    nr+=(1<<bit);
                }
            }
        }
        int x=0;
        for(int bit=20;bit>=0;bit--)
        {
            if((s[i]>>bit)&1)
                x+=(1<<bit);
            f[x][bit]=i;
        }
    }
    if(l==0&&r==0)
    {
        fout<<s[1]<<" "<<1<<" "<<1;
        return 0;
    }
    fout<<ans<<" "<<l<<" "<<r;
    return 0;
}