Submission #875557

#	Time	Username	Problem	Language	Result	Execution time	Memory
875557		The_Samurai	XOR (IZhO12_xor)	C++17	100 / 100	1151 ms	88976 KiB

xor

// #pragma GCC optimize("Ofast,O3")
// #pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

void solve() {
    int n, c;
    cin >> n >> c;
    vector<int> a(n + 1), pref(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] ^ a[i];
    pair<int, int> ans = make_pair(0, 0);
    auto upd = [&](int l, int r) -> void {
        if (ans.second > r - l + 1) return;
        if (ans.second < r - l + 1) ans = make_pair(l, r - l + 1);
        else ans.first = min(ans.first, l);
    };
    vector<map<int, int>> have(30);
    for (int i = 0; i < 30; i++) have[i][0] = 0;


    for (int i = 1; i <= n; i++) {
        // pref[i] ^ pref[x] >= c
        int now = 0, j = 29;
        for (; j >= 0; j--) {
            if (c & (1 << j)) {
                now |= (pref[i] & (1 << j) ? 0 : 1 << j);
                if (!have[j].count(now)) break;
            } else {
                if (pref[i] & (1 << j)) {
                    if (have[j].count(now)) {
                        upd(have[j][now] + 1, i);
                        break;
                    }
                    now |= 1 << j;
                    assert(have[j][now]);
                    continue;
                }
                if (have[j].count(now | (1 << j))) {
                    upd(have[j][now | (1 << j)] + 1, i);
                    break;
                }
            }
        }
        if (j < 0) upd(have[0][now] + 1, i);
        now = 0;
        for (j = 29; j >= 0; j--) {
            now |= pref[i] & (1 << j);
            if (!have[j][now]) have[j][now] = i;
        }
    }
    cout << ans.first << ' ' << ans.second;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
    // cin >> q;
    while (q--) {
        solve();
        cout << '\n';
    }
}

• Subtask 1: 100 / 100