Submission #1196733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196733		m_elgamal	XOR (IZhO12_xor)	C++17	100 / 100	395 ms	72080 KiB

xor

#include "bits/stdc++.h"
#define ll long long
#define el '\n'
using namespace std;

// We maintain prefix-xor of the array as we go, and store all previous prefix-xors in a binary trie.
// For each new prefix, we query the trie for the earliest previous prefix-j such that
// prefix[i] ^ prefix[j] >= x, which means the subarray (j+1 .. i) has xor >= x.

// Map to record the earliest index at which each prefix-xor value appeared
map<ll, int> eq;

class BinaryTrie {
private:
    struct Node {
        Node* ch[2];         // child pointers for bit 0 and bit 1
        int fr;              // frequency count (not used in query, but kept for potential extensions)
        int minIdx;          // minimum prefix-index stored in this subtree
        Node() : fr(0), minIdx(INT_MAX) {
            memset(ch, 0, sizeof ch);
        }
    };

public:
    Node* root = new Node();

    // Initialize trie by inserting prefix-xor = 0 at index 0
    BinaryTrie() {
        insert(0, 0);
    }

    // Insert a prefix-xor value x with its index idx into the trie
    void insert(ll x, int idx) {
        Node* cur = root;
        // update root's minIdx
        cur->minIdx = min(cur->minIdx, idx);
        // Traverse bits from most-significant (62) down to 0
        for (int i = 62; i >= 0; i--) {
            int bit = (x >> i) & 1;
            if (!cur->ch[bit])
                cur->ch[bit] = new Node();
            cur = cur->ch[bit];
            cur->fr++;
            // update the subtree's minimum index
            cur->minIdx = min(cur->minIdx, idx);
        }
    }

    // Query for the earliest prefix-index j such that (y ^ prefix[j]) >= x.
    // We walk the trie bit-by-bit, and whenever x's bit is 0, taking the opposite branch
    // would make the result-bit = 1 > 0, ensuring the overall xor > x at that bit.
    int query(ll y, ll x) {
        Node* cur = root;
        int mn = INT_MAX;
        for (int i = 62; i >= 0 && cur; i--) {
            int xb = (x >> i) & 1;  // bit i of target x
            int yb = (y >> i) & 1;  // bit i of current prefix

            // eqBranch = branch that keeps result-bit == xb
            int eqBranch = xb ^ yb;
            // otherBranch would flip the result-bit to 1-xb
            int otherBranch = 1 ^ eqBranch;

            // If xb==0, we can exceed x by picking otherBranch (makes result-bit==1)
            if (xb == 0 && cur->ch[otherBranch]) {
                // any prefix in that subtree gives result >= x, pick earliest
                mn = min(mn, cur->ch[otherBranch]->minIdx + 1);
            }
            // Continue down the branch that keeps result-bit == xb
            cur = cur->ch[eqBranch];
        }
        // If we consumed all bits and still in trie, result==x exactly; still valid
        if (cur) {
            mn = min(mn, cur->minIdx + 1);
        }
        return mn;
    }
};

void solve() {
    ll n, x;
    cin >> n >> x;

    BinaryTrie trie;
    ll pre = 0;               // current prefix-xor
    int bestL = -1, bestK = -1;

    // Process each array element, updating prefix-xor
    for (int i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        pre ^= a;

        // Record earliest occurrence of this prefix-xor value
        eq[pre] = (eq.count(pre) ? eq[pre] : i);

        // Query trie for earliest j where pre ^ prefix[j] >= x
        int j = trie.query(pre, x);
        if (j <= i) {
            int len = i - j + 1;
            // Update best interval if longer found
            if (bestK == -1 || len > bestK) {
                bestK = len;
                bestL = j;
            }
        }
        // Insert current prefix-xor with its index into trie
        trie.insert(pre, i);
    }

    // Output starting index and length of the longest valid subarray
    cout << bestL << " " << bestK << el;
}

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

    // Optional file redirection if input.txt exists
    if (fopen("input.txt", "r")) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100