Submission #1318015

#TimeUsernameProblemLanguageResultExecution timeMemory
1318015keroXOR (IZhO12_xor)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>
using namespace std;

/* ==== BinaryTrie template (زي ما بعته) ==== */
struct TrieNode {
    TrieNode* child[2];
    int cnt;
    TrieNode() {
        child[0] = child[1] = nullptr;
        cnt = 0;
    }
};

class BinaryTrie {
public:
    static const int MAXB = 31;
    TrieNode* root;

    BinaryTrie() {
        root = new TrieNode();
    }

    void insert(int x, int delta = 1) {
        TrieNode* cur = root;
        cur->cnt += delta;
        for (int b = MAXB; b >= 0; b--) {
            int bit = (x >> b) & 1;
            if (!cur->child[bit])
                cur->child[bit] = new TrieNode();
            cur = cur->child[bit];
            cur->cnt += delta;
        }
    }

    long long countXorLessThan(int x, int k) {
        TrieNode* cur = root;
        long long res = 0;
        for (int b = MAXB; b >= 0; b--) {
            if (!cur) break;
            int xb = (x >> b) & 1;
            int kb = (k >> b) & 1;
            if (kb == 1) {
                if (cur->child[xb])
                    res += cur->child[xb]->cnt;
                cur = cur->child[1 - xb];
            } else {
                cur = cur->child[xb];
            }
        }
        return res;
    }

    long long countXorGreaterThan(int x, int k) {
        long long total = root->cnt;
        long long less = countXorLessThan(x, k + 1);
        return total - less;
    }
};
/* ======================================== */

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

    int N;
    int X;
    cin >> N >> X;

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

    px[0] = 0;
    for (int i = 1; i <= N; i++)
        px[i] = px[i - 1] ^ a[i];

    BinaryTrie trie;

    int l = 1;
    int bestLen = 0, bestI = 1;

    trie.insert(px[0], 1);

    for (int r = 1; r <= N; r++) {
        // حاول تقلل l لحد ما يبقى فيه حل
        while (l <= r &&
               trie.countXorGreaterThan(px[r], X - 1) == 0) {
            trie.insert(px[l - 1], -1);
            l++;
        }

        if (l <= r) {
            int len = r - l + 1;
            if (len > bestLen) {
                bestLen = len;
                bestI = l;
            }
        }

        trie.insert(px[r], 1);
    }

    cout << bestI << " " << bestLen << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...