Submission #588586

#	Time	Username	Problem	Language	Result	Execution time	Memory
588586		leeh18	XOR (IZhO12_xor)	C++17	100 / 100	577 ms	59396 KiB

xor

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

struct trie_node {
    int max_idx;
    array<unique_ptr<trie_node>, 2> children;
    trie_node() : max_idx(0) {}
    void insert(int x, int idx, int pos = 30) {
        if (pos < 0) return;
        int bit = (x >> pos) & 1;
        if (children[bit] == nullptr) {
            children[bit] = make_unique<trie_node>();
        }
        children[bit]->max_idx = max(children[bit]->max_idx, idx);
        children[bit]->insert(x, idx, pos-1);
    }
    bool check(int bit, int k) {
        if (children[bit] == nullptr) return false;
        return children[bit]->max_idx >= k;
    }
    int max_xor(int x, int k, int pos = 30) {
        if (pos < 0) return 0;
        int ret = 0;
        int bit = (x >> pos) & 1;
        if (check(bit^1, k)) {
            ret = children[bit^1]->max_xor(x, k, pos-1);
            ret |= (1 << pos);
        } else {
            ret = children[bit]->max_xor(x, k, pos-1);
        }
        return ret;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int n, x;
    cin >> n >> x;
    vector<int> psum(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> psum[i];
        psum[i] ^= psum[i - 1];
    }
    trie_node trie;
    for (int i = 0; i <= n; i++) {
        trie.insert(psum[i], i);
    }
    int ans_i = 0, ans_k = 0;
    for (int i = 0; i < n; i++) {
        int lo = i, hi = n;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (trie.max_xor(psum[i], mid) >= x) lo = mid;
            else hi = mid - 1;
        }
        int k = lo - i;
        if (ans_k < k) {
            ans_i = i + 1;
            ans_k = k;
        }
    }
    cout << ans_i << ' ' << ans_k << '\n';
}

• Subtask 1: 100 / 100