Submission #1196725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196725		m_elgamal	XOR (IZhO12_xor)	C++17	100 / 100	115 ms	27028 KiB

xor

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

struct Node {
    int ch[2]{-1,-1};
    int maxIdx = -1;                 // largest suffix index in this subtree
};

struct Trie {
    static constexpr int BITS = 31;  // numbers < 2^31
    vector<Node> t = {Node{}};       // node 0 is the root

    int newNode() { t.push_back(Node{}); return (int)t.size() - 1; }

    void insert(int val, int idx) {
        int v = 0;
        t[v].maxIdx = max(t[v].maxIdx, idx);
        for (int b = BITS-1; b >= 0; --b) {
            int bit = (val >> b) & 1;
            if (t[v].ch[bit] == -1) t[v].ch[bit] = newNode();
            v = t[v].ch[bit];
            t[v].maxIdx = max(t[v].maxIdx, idx);
        }
    }

    // largest j such that  val ^ stored >= x   (-1 if none)
    int query(int val, int x) const {
        int v = 0;
        int best = -1;                       // best index seen so far

        for (int b = BITS-1; b >= 0 && v != -1; --b) {
            int vb = (val >> b) & 1;
            int xb = (x   >> b) & 1;

            if (xb == 1) {                   // xor bit must be 1
                v = t[v].ch[vb ^ 1];
            } else {                         // xor bit 0 or 1 are both OK
                int candNode = t[v].ch[vb ^ 1];
                if (candNode != -1) best = max(best, t[candNode].maxIdx);
                v = t[v].ch[vb];             // keep xor equal, continue
            }
        }
        if (v != -1) best = max(best, t[v].maxIdx);   // xor == x exactly
        return best;
    }
};

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

    int N; int X;
    if (!(cin >> N >> X)) return 0;
    vector<int> a(N);
    for (int &v : a) cin >> v;

    /* build suffix xor array */
    vector<int> S(N + 1, 0);                 // S[N] = 0
    for (int i = N - 1; i >= 0; --i) S[i] = S[i + 1] ^ a[i];

    Trie trie;
    trie.insert(S[N], N);                    // empty suffix

    int bestLen = 0, bestI = N;              // 1-based output later

    for (int i = N - 1; i >= 0; --i) {
        trie.insert(S[i], i);                // make S[i] available
        int j = trie.query(S[i], X);         // j > i, or –1 (not possible here)
        int len = j - i;
        if (len > bestLen || (len == bestLen && i < bestI)) {
            bestLen = len;
            bestI = i;
        }
    }
    cout << bestI + 1 << ' ' << bestLen << '\n';
    return 0;
}

• Subtask 1: 100 / 100