Submission #881167

#	Time	Username	Problem	Language	Result	Execution time	Memory
881167		alexdd	XOR (IZhO12_xor)	C++17	100 / 100	126 ms	44376 KiB

xor

#include<iostream>
#include<unordered_map>
#include<map>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
int n,x;
int fr[8000005];
int trie[8000005][2];
int cntt;
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;
        if(a>=x && i>maxlun)
        {
            maxlun=i;
            pozmax=i;
        }
        int pref=0,prefx=0;
        for(int j=29;j>=0;j--)
        {
            if(j==29 || prefx!=0)
            {
                if(((1<<j)&x)==0)
                {
                    ///pref ^ y == prefx + (1<<j)
                    int newx = 0;
                    if(((1<<j)&x) == ((1<<j)&a))
                        newx = trie[prefx][1];
                    else
                        newx = trie[prefx][0];
                    if(newx!=0)
                    {
                        curlun = i + fr[newx] - 300000;
                        if(curlun > maxlun)
                        {
                            maxlun = curlun;
                            pozmax=i;
                        }
                    }
                }
                if(((1<<j)&x) != ((1<<j)&a))
                {
                    if(trie[prefx][1]==0)
                        trie[prefx][1]=++cntt;
                    prefx = trie[prefx][1];
                }
                else
                {
                    if(trie[prefx][0]==0)
                        trie[prefx][0]=++cntt;
                    prefx = trie[prefx][0];
                }
            }
            if(((1<<j)&a))
            {
                if(trie[pref][1]==0)
                    trie[pref][1]=++cntt;
                pref = trie[pref][1];
            }
            else
            {
                if(trie[pref][0]==0)
                    trie[pref][0]=++cntt;
                pref = trie[pref][0];
            }
            fr[pref] = max(fr[pref], -i + 300000);
        }
        ///a ^ y == x
        if(prefx!=0)
        {
            curlun = i + fr[prefx] - 300000;
            if(curlun > maxlun)
            {
                maxlun = curlun;
                pozmax=i;
            }
        }
    }
    cout<<pozmax-maxlun+1<<" "<<maxlun;
    return 0;
}

• Subtask 1: 100 / 100