Submission #933866

#	Time	Username	Problem	Language	Result	Execution time	Memory
933866		thinknoexit	XOR (IZhO12_xor)	C++17	100 / 100	641 ms	14408 KiB

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 / 100