Submission #1112228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112228		Kirill22	XOR (IZhO12_xor)	C++17	100 / 100	133 ms	55508 KiB

xor

#include "bits/stdc++.h"

using namespace std;

int nxt[(int) 1e7][2], dp[(int) 1e7], cnt = 2;

void add(int v, int x, int j, int i) {
    if (j == -1) {
        dp[v] = min(dp[v], i);
    } else {
        if (x >> j & 1) {
            if (!nxt[v][1]) nxt[v][1] = cnt++;
            add(nxt[v][1], x, j - 1, i);
        } else {
            if (!nxt[v][0]) nxt[v][0] = cnt++;
            add(nxt[v][0], x, j - 1, i);
        }
        dp[v] = min(dp[nxt[v][0]], dp[nxt[v][1]]);
    }
}

int get(int v, int have, int need, int j) {
    if (!v) {
        return (int) 1e9;
    }
    if (j == -1) {
        return dp[v];
    }
    int bit = (have >> j & 1) ^ (need >> j & 1);
    int res = get(nxt[v][bit], have, need, j - 1);
    if ((need >> j & 1) == 0) {
        res = min(res, dp[nxt[v][1 - (have >> j & 1)]]);
    }
    return res;
}

mt19937 gen(22);

void solve() {
    int n, x;
    cin >> n >> x;
    pair<int, int> ans = {0, 0};
    fill(dp, dp + (int) 1e7, n);
    for (int i = 0, sum = 0; i < n; i++) {
        int val = gen() % 16;
        cin >> val;
        add(1, sum, 30, i);
        sum ^= val;
        int l = get(1, sum, x, 30);
        if (l <= i && i - l + 1 > ans.second) {
            ans = {l, i - l + 1};
        }
    }
    cout << ans.first + 1 << " " << ans.second << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 100 / 100