oj.uz

Submission #881124

# Submission time Handle Problem Language Result Execution time Memory
881124 2023-11-30T15:59:36 Z alexdd XOR (IZhO12_xor) C++17
0 / 100
 2000 ms 143100 KB 
#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.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 348 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 16 ms 2996 KB Output is correct
6 Correct 29 ms 3756 KB Output is correct
7 Correct 20 ms 3256 KB Output is correct
8 Correct 23 ms 4080 KB Output is correct
9 Correct 634 ms 57080 KB Output is correct
10 Correct 638 ms 58944 KB Output is correct
11 Correct 684 ms 55336 KB Output is correct
12 Correct 524 ms 53012 KB Output is correct
13 Correct 517 ms 50844 KB Output is correct
14 Correct 566 ms 53788 KB Output is correct
15 Correct 718 ms 67376 KB Output is correct
16 Correct 496 ms 51096 KB Output is correct
17 Execution timed out 2017 ms 143100 KB Time limit exceeded
18 Halted 0 ms 0 KB -