Submission #1194164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194164		madamadam3	XOR (IZhO12_xor)	C++20	0 / 100	0 ms	320 KiB

xor

#include <bits/stdc++.h>

using namespace std;

/*
    SAPO 2025 TC4 Day 2 - Largest Subarray
    copied from IZhO 2012 - XOR

    SAPO breakdown was:
    n <= 10^5, c[i] < 2^30
    - subtask 1 (40 pts): n <= 5000
    - subtask 2 (60 pts): no further constraints

    40/100 pt solution here
*/

// int main() {
//     cin.tie(0)->sync_with_stdio(0);

//     int n, x; cin >> n >> x;
//     vector<int> c(n); for (int i = 0; i < n; i++) cin >> c[i];
//     vector<int> prefix(n + 1, 0); for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] ^ c[i - 1];

//     int best_idx = 0;
//     int best_k = 0;

//     for (int i = 0; i < n; i++) {
//         for (int k = best_k + 1; i + k - 1 < n; k++) {
//             int r = i + k - 1;
//             if ((prefix[r + 1] ^ prefix[i]) >= x) {
//                 best_idx = i;
//                 best_k = k;
//             }
//         }
//     }

//     cout << best_idx + 1 << " " << best_k;
//     return 0;
// }

struct Node {
    Node* children[2];
    int first_idx;

    Node(int idx) {
        children[0] = children[1] = nullptr;
        first_idx = idx;
    }
};

struct Trie {
    Node* root;

    void insert(int num, int idx) {
        Node* cur = root;
        cur->first_idx = max(cur->first_idx, idx);        
        for (int i = 31; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (!cur->children[bit]) cur->children[bit] = new Node(idx);
            cur = cur->children[bit];
            cur->first_idx = max(cur->first_idx, idx);
        }
    }


    int query(int num, int x) {
        Node* cur = root;
        int val = 0;

        for (int i = 31; i >= 0; i--) {
            if (val >= x) return cur->first_idx;

            int desired = ((num >> i) & 1) ^ 1;         
            int go = cur->children[desired] ? desired : desired ^ 1;
            int xor_bit = ((num >> i) & 1) ^ go;
            val |= (xor_bit << i);
            cur = cur->children[go];
        }

        return cur->first_idx;
    }

    Trie() {
        this->root = new Node(-1);
    }
};


int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, x; cin >> n >> x;
    vector<int> c(n); for (int i = 0; i < n; i++) cin >> c[i];
    vector<int> sxor(n + 1, 0);

    auto trie = Trie();
    trie.insert(0, n);
    int ansidx = n, anslen = 0;

    for (int i = n - 1; i >= 0; i--) {
        sxor[i] = sxor[i+1] ^ c[i];
        trie.insert(sxor[i], i);

        int j = trie.query(sxor[i], x);    
        int ans = j - i;  
        if (ans >= anslen) {
            ansidx = i;
            anslen = ans;
        }
    }

    cout << ansidx+1 << " " << anslen;
    return 0;
}

• Subtask 1: 0 / 100