Submission #1271548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271548		ashishlimitless	XOR (IZhO12_xor)	C++20	100 / 100	118 ms	56552 KiB

xor

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

using LL = long long;

const int B = 30; // bit length

struct TrieNode {
    TrieNode* nxt[2];
    int minIdx;
    TrieNode() {
        nxt[0] = nxt[1] = nullptr;
        minIdx = INT_MAX;
    }
};

struct Trie {
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(int val, int idx) {
        TrieNode* cur = root;
        for (int bit = B - 1; bit >= 0; bit--) {
            int b = (val >> bit) & 1;
            if (!cur->nxt[b]) cur->nxt[b] = new TrieNode();
            cur = cur->nxt[b];
            cur->minIdx = min(cur->minIdx, idx);
        }
    }

    int query(int x, int k) {
        TrieNode* cur = root;
        int ans = INT_MAX;
        for (int bit = B - 1; bit >= 0; bit--) {
            if (!cur) break;
            int xb = (x >> bit) & 1;
            int kb = (k >> bit) & 1;
            if (!kb) {
                if (cur->nxt[xb ^ 1]) ans = min(ans, cur->nxt[xb ^ 1]->minIdx);
                cur = cur->nxt[xb];
            } else {
                cur = cur->nxt[xb ^ 1];
            }
        }
        if (cur) ans = min(ans, cur->minIdx);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    Trie trie;
    int pref = 0;
    trie.insert(pref, 0);

    int ans = 0, ans_id = -1;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        pref ^= x;
        int idx = trie.query(pref, k);
        if (idx != INT_MAX) {
            if (i - idx > ans) ans = i - idx, ans_id = idx;
            else if (i - idx == ans) ans_id = min(ans_id, idx);
        }
        trie.insert(pref, i);
    }

    cout << ++ans_id << ' ' << ans << '\n';
    return 0;
}

• Subtask 1: 100 / 100