Submission #881124

#	Time	Username	Problem	Language	Result	Execution time	Memory
881124		alexdd	XOR (IZhO12_xor)	C++17	0 / 100	2017 ms	143100 KiB

xor

#include<iostream>
#include<unordered_map>
#include<map>
//#pragma GCC optimize("O3,unroll-loops")
using namespace std;
int n,x;
unordered_map<int,int> fr[30];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>x;
    int a,maxlun=0,pozmax=0,curlun,sump=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        sump ^= a;
        a = sump;
        ///a ^ y == x
        curlun = i + fr[0][(a^x)] - 300000;
        if(fr[0][(a^x)]!=0 && curlun > maxlun)
        {
            maxlun = curlun;
            pozmax=i;
        }
        int pref=0,prefx=0;
        for(int j=29;j>=0;j--)
        {
            if(((1<<j)&a))
                pref += (1<<j);
            if(((1<<j)&x))
                prefx += (1<<j);
            if(((1<<j)&x)==0)
            {
                ///pref ^ y == prefx + (1<<j)
                curlun = i + fr[j][(pref^(prefx+(1<<j)))] - 300000;
                if(fr[j][(pref^(prefx+(1<<j)))]!=0 && curlun > maxlun)
                {
                    maxlun = curlun;
                    pozmax=i;
                }
            }
            fr[j][pref] = max(fr[j][pref], -i + 300000);
        }

    }
    cout<<pozmax-maxlun+1<<" "<<maxlun;
    return 0;
}

• Subtask 1: 0 / 100