제출 #1268245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268245		iamarman	XOR (IZhO12_xor)	C++20	0 / 100	789 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;
        // use bits 30..0 (numbers <= 1e9 < 2^30)
        for (int i = 30; 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++;
        }
    }

    int max_xor(int n) {
        TrieNode *curr = root;
        int ans = 0;
        for (int i = 30; 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;
    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 xor
    vector<int> P(N+1, 0);
    for (int i = 1; i <= N; ++i) P[i] = P[i-1] ^ a[i];

    if (x == 0) {
        cout << 1 << " " << N << "\n";
        return 0;
    }

    auto exists_len_at_least = [&](int len)->bool {
        Trie t;
        t.insert(P[0]); // prefix 0
        // for r = len..N, we need P[0..r-len] in trie before checking P[r]
        for (int r = len; r <= N; ++r) {
            if (r > len) t.insert(P[r - len]); // insert new prefix
            int best = t.max_xor(P[r]);
            if (best >= x) return true;
        }
        return false;
    };

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

    // find smallest starting index for length exactly bestLen
    int ans_i = -1;
    for (int r = bestLen; r <= N; ++r) {
        int val = P[r] ^ P[r - bestLen];
        if (val >= x) {
            ans_i = r - bestLen + 1;
            break;
        }
    }

    cout << ans_i << " " << bestLen << "\n";
    return 0;
}

• Subtask 1: 0 / 100