Submission #933866

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
933866	2024-02-26T12:39:56 Z	thinknoexit	XOR (IZhO12_xor)	C++17	100 / 100	641 ms	14408 KB

xor

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 250500;
int a[N];
map<int, int> mp;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, x;
    cin >> n >> x;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    int idx = 0, ans = -1;
    int now = 0;
    for (int bit = 30;bit >= 0;bit--) {
        now |= (1 << bit);
        if (x & (1 << bit)) continue;
        mp[0] = 0;
        int val = 0;
        for (int i = 1;i <= n;i++) {
            val ^= (a[i] & now);
            if (mp.count(now ^ val)) {
                int pos = mp[now ^ val];
                if (i - pos > ans) {
                    ans = i - pos;
                    idx = pos + 1;
                }
            }
            if (!mp.count(val)) mp[val] = i;
        }
        mp.clear();
        now ^= (1 << bit);
    }
    mp[0] = 0;
    int val = 0;
    for (int i = 1;i <= n;i++) {
        val ^= (a[i] & x);
        if (mp.count(x ^ val)) {
            int pos = mp[x ^ val];
            if (i - pos > ans) {
                ans = i - pos;
                idx = pos + 1;
            }
        }
        if (!mp.count(val)) mp[val] = i;
    }
    cout << idx << ' ' << ans;
    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	1 ms	464 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	7 ms	1372 KB	Output is correct
6	Correct	14 ms	1616 KB	Output is correct
7	Correct	10 ms	1628 KB	Output is correct
8	Correct	10 ms	1628 KB	Output is correct
9	Correct	171 ms	6260 KB	Output is correct
10	Correct	170 ms	6188 KB	Output is correct
11	Correct	141 ms	5972 KB	Output is correct
12	Correct	137 ms	6220 KB	Output is correct
13	Correct	107 ms	6228 KB	Output is correct
14	Correct	132 ms	6028 KB	Output is correct
15	Correct	226 ms	5868 KB	Output is correct
16	Correct	111 ms	6444 KB	Output is correct
17	Correct	600 ms	13652 KB	Output is correct
18	Correct	619 ms	14408 KB	Output is correct
19	Correct	641 ms	12704 KB	Output is correct
20	Correct	420 ms	14164 KB	Output is correct