Submission #881167

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
881167	2023-11-30T17:13:22 Z	alexdd	XOR (IZhO12_xor)	C++17	100 / 100	126 ms	44376 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	6 ms	1456 KB	Output is correct
6	Correct	8 ms	1528 KB	Output is correct
7	Correct	7 ms	1628 KB	Output is correct
8	Correct	8 ms	1688 KB	Output is correct
9	Correct	40 ms	20308 KB	Output is correct
10	Correct	41 ms	20164 KB	Output is correct
11	Correct	40 ms	20184 KB	Output is correct
12	Correct	41 ms	20144 KB	Output is correct
13	Correct	47 ms	20492 KB	Output is correct
14	Correct	42 ms	20304 KB	Output is correct
15	Correct	41 ms	20304 KB	Output is correct
16	Correct	40 ms	20308 KB	Output is correct
17	Correct	113 ms	42324 KB	Output is correct
18	Correct	117 ms	44376 KB	Output is correct
19	Correct	117 ms	44308 KB	Output is correct
20	Correct	126 ms	44352 KB	Output is correct