Submission #881123

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
881123	2023-11-30T15:58:37 Z	alexdd	XOR (IZhO12_xor)	C++17	0 / 100	2000 ms	149892 KB

xor

#include<iostream>
#include<map>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
int n,x;
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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	4 ms	860 KB	Output is correct
5	Correct	50 ms	3160 KB	Output is correct
6	Correct	71 ms	3840 KB	Output is correct
7	Correct	64 ms	3620 KB	Output is correct
8	Correct	75 ms	3664 KB	Output is correct
9	Correct	767 ms	62112 KB	Output is correct
10	Correct	818 ms	63192 KB	Output is correct
11	Correct	655 ms	58048 KB	Output is correct
12	Correct	778 ms	57816 KB	Output is correct
13	Correct	637 ms	53824 KB	Output is correct
14	Correct	691 ms	57052 KB	Output is correct
15	Correct	771 ms	71908 KB	Output is correct
16	Correct	607 ms	54100 KB	Output is correct
17	Execution timed out	2031 ms	149892 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-