Submission #1268243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268243		iamarman	XOR (IZhO12_xor)	C++20	0 / 100	792 ms	327680 KiB

xor

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

class TrieNode {
public:
    TrieNode *left;   // bit 0
    TrieNode *right;  // bit 1
    int cnt;
    TrieNode(): left(nullptr), right(nullptr), cnt(0) {}
};

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

    void insert(int n) {
        TrieNode *curr = root;
        for (int i = 31; i >= 0; --i) {
            int bit = (n >> i) & 1;
            if (bit == 0) {
                if (!curr->left) curr->left = new TrieNode();
                curr = curr->left;
            } else {
                if (!curr->right) curr->right = new TrieNode();
                curr = curr->right;
            }
            curr->cnt++;
        }
    }

    // return the maximum xor we can get with `n` against any value in trie
    int max_xor(int n) {
        TrieNode *curr = root;
        int ans = 0;
        for (int i = 31; i >= 0; --i) {
            if (!curr) break;
            int bit = (n >> i) & 1;
            if (bit == 0) {
                if (curr->right && curr->right->cnt > 0) {
                    ans |= (1 << i);
                    curr = curr->right;
                } else {
                    curr = curr->left;
                }
            } else {
                if (curr->left && curr->left->cnt > 0) {
                    ans |= (1 << i);
                    curr = curr->left;
                } else {
                    curr = curr->right;
                }
            }
        }
        return ans;
    }
};

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

    int N;
    long long x_ll; // x fits in 32-bit but read as long long safe
    if (!(cin >> N >> x_ll)) return 0;
    int x = (int)x_ll;

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

    // prefix xors P[0..N]
    vector<int> P(N+1, 0);
    for (int i = 1; i <= N; ++i) P[i] = P[i-1] ^ a[i];

    // Quick handle: if x == 0, any subarray qualifies; answer is whole array (smallest i = 1)
    if (x == 0) {
        cout << 1 << " " << N << "\n";
        return 0;
    }

    // check if there exists a subarray with length >= len whose xor >= x
    auto exists_len_at_least = [&](int len) -> bool {
        Trie t;
        // we will insert P[0.. r-len ] as r increases
        t.insert(P[0]); // prefix index 0
        for (int r = len; r <= N; ++r) {
            // For r=len, inserted P[0], check P[len]
            // For larger r, before checking insert P[r-len]
            if (r > len) t.insert(P[r - len]);
            int best = t.max_xor(P[r]);
            if (best >= x) return true;
        }
        return false;
    };

    // binary search maximum k
    int lo = 1, hi = N, bestLen = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (exists_len_at_least(mid)) {
            bestLen = mid;
            lo = mid + 1;
        } else hi = mid - 1;
    }

    // find smallest start index i for length exactly bestLen
    // Because bestLen is maximal, any valid pair of length >= bestLen must have length == bestLen.
    int ans_i = -1;
    for (int r = bestLen; r <= N; ++r) {
        int val = P[r] ^ P[r - bestLen]; // xor of subarray starting at s = r-bestLen+1
        if (val >= x) {
            ans_i = r - bestLen + 1; // 1-based start index
            break; // smallest i we encounter while r grows => minimal start
        }
    }

    // Output i and k
    cout << ans_i << " " << bestLen << "\n";
    return 0;
}

• Subtask 1: 0 / 100