Submission #1222712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222712		silence25	XOR (IZhO12_xor)	C++20	100 / 100	236 ms	60500 KiB

xor

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

struct TrieNode {
    TrieNode* child[2]; // Array of pointers for 0 and 1
    int min_index;      // Store the minimum index for this path
    TrieNode() {
        child[0] = child[1] = nullptr;
        min_index = INT_MAX;
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(long long x, int index) {
        TrieNode* node = root;
        for (int i = 63; i >= 0; --i) {
            int bit = (x >> i) & 1;
            if (!node->child[bit]) { // Check if child exists
                node->child[bit] = new TrieNode();
            }
            node = node->child[bit]; // Move to the child node
        }
        node->min_index = min(node->min_index, index); // Update minimum index
    }

    pair<long long, int> query_max_xor(long long x) {
        TrieNode* node = root;
        long long result = 0;
        for (int i = 63; i >= 0; --i) {
            int bit = (x >> i) & 1;
            if (node->child[1 - bit]) { // Prefer the opposite bit to maximize XOR
                result |= (1LL << i);
                node = node->child[1 - bit];
            } else if (node->child[bit]) {
                node = node->child[bit];
            } else {
                return {0, INT_MAX}; // No valid path
            }
        }
        return {result, node->min_index}; // Return max XOR and min index
    }
};

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

    int N;
    long long x;
    cin >> N >> x;
    vector<long long> a(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> a[i];
    }

    // Compute prefix XORs
    vector<long long> pref(N + 1);
    pref[0] = 0;
    for (int i = 1; i <= N; ++i) {
        pref[i] = pref[i - 1] ^ a[i];
    }

    Trie trie;
    int max_k = 0;
    int best_i = 1;
    trie.insert(pref[0], 0); // Insert pref[0] = 0 at index 0
    for (int j = 1; j <= N; ++j) {
        // Query for max XOR with pref[j]
        auto [xor_val, i_minus_1] = trie.query_max_xor(pref[j]);
        if (xor_val >= x && i_minus_1 < j) {
            int i = i_minus_1 + 1;
            int k = j - i + 1;
            if (k > max_k) {
                max_k = k;
                best_i = i;
            }
        }
        // Insert pref[j-1] into Trie
        trie.insert(pref[j - 1], j - 1);
    }

    cout << best_i << " " << max_k << endl;

    return 0;
}

• Subtask 1: 100 / 100