oj.uz

Submission #881125

# Submission time Handle Problem Language Result Execution time Memory
881125 2023-11-30T16:01:45 Z alexdd XOR (IZhO12_xor) C++17
0 / 100
 2000 ms 142836 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(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(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 860 KB Output is correct
5 Correct 18 ms 3000 KB Output is correct
6 Correct 21 ms 4020 KB Output is correct
7 Correct 20 ms 3256 KB Output is correct
8 Correct 23 ms 4004 KB Output is correct
9 Correct 736 ms 57364 KB Output is correct
10 Correct 868 ms 58616 KB Output is correct
11 Correct 733 ms 55084 KB Output is correct
12 Correct 712 ms 52968 KB Output is correct
13 Correct 723 ms 50960 KB Output is correct
14 Correct 797 ms 53688 KB Output is correct
15 Correct 931 ms 67320 KB Output is correct
16 Correct 672 ms 51096 KB Output is correct
17 Execution timed out 2083 ms 142836 KB Time limit exceeded
18 Halted 0 ms 0 KB -