Submission #479875

#	Time	Username	Problem	Language	Result	Execution time	Memory
479875		ogibogi2004	XOR (IZhO12_xor)	C++14	100 / 100	1422 ms	15848 KiB

xor

#include<bits/stdc++.h>
using namespace std;
const int MAXN=250002;
int n,x;
int maxbit=30;
int a[MAXN],cur=0;
pair<int,int>ans;
int pref[MAXN];
map<int,int>seen_when;
int main()
{
    cin>>n>>x;
    ans={0,0};
    seen_when[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        pref[i]=pref[i-1]^a[i];
        if(seen_when.count(x^pref[i]))
        {
            ans=max(ans,{i-seen_when[x^pref[i]],-seen_when[x^pref[i]]-1});
        }
        if(seen_when.count(pref[i])==0)
        {
            seen_when[pref[i]]=i;
        }
        if(a[i]>=x)
        {
            ans=max(ans,{1,-i});
        }
    }
    for(int i=maxbit;i>=0;i--)
    {
        if(!(x&(1<<i)))
        {
            int to_try=cur+(1<<i);
            //cout<<to_try<<endl;
            seen_when.clear();
            seen_when[0]=0;
            for(int j=1;j<=n;j++)
            {
                //cout<<pref[j]<<" ";
                pref[j]=pref[j-1]^(a[j]&to_try);
                if(seen_when.count(to_try^pref[j]))
                {
                    ans=max(ans,{j-seen_when[to_try^pref[j]],-seen_when[to_try^pref[j]]-1});
                }
                if(seen_when.count(pref[j])==0)
                {
                    seen_when[pref[j]]=j;
                }
            }
            //cout<<endl;
            //cout<<ans.first<<" "<<ans.second<<endl;
        }
        else cur+=(1<<i);
    }
    cout<<-ans.second<<" "<<ans.first<<endl;
return 0;
}

• Subtask 1: 100 / 100