Submission #1266192

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

xor

#include <bits/stdc++.h>
using namespace std;
const int mxN = 550005;
#define int long long

int a[mxN];

struct Node {
    Node* children[2];
    int mn_idx;
    Node() {
        children[0] = children[1] = NULL;
        mn_idx = mxN;
    }
};

struct Trie {
    Node* root = new Node();
    void add(int val, int idx) {
        Node* curr = root;
        for (int i = 32; i >= 0; --i) {
            int curr_bit = (val >> i) & 1;
            if (curr->children[curr_bit] == NULL)
                curr->children[curr_bit] = new Node();
            curr = curr->children[curr_bit];
            curr->mn_idx = min(curr->mn_idx, idx);
        }
    }
    int query(int val, int x) {
        Node* curr = root;
        if (!curr) return mxN;
        int idx = mxN;
        int xor_val = 0;
        for (int i = 32; i >= 0; --i) {
            int bit = (val >> i) & 1;
            int xbit = (x >> i) & 1;
            if (xbit == 1) {
                if (curr->children[1 - bit])
                    idx = min(idx, curr->children[1 - bit]->mn_idx);
                if (curr->children[bit])
                    curr = curr->children[bit];
                else
                    break;
            } else {
                if (curr->children[1 - bit]) {
                    curr = curr->children[1 - bit];
                } else if (curr->children[bit]) {
                    curr = curr->children[bit];
                } else break;
            }
        }
        return idx;
    }
} tr;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int n, x;
    cin >> n >> x;
    int pref = 0;

    tr.add(0, 0);

    pair<int, int> ans = {0, 0}; 

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pref ^= a[i];

        int idx = tr.query(pref, x); 
        if (idx != mxN) {
            int len = i - idx;
            if (len > ans.first) {
                ans = {len, idx + 1}; 
            }
        }

        tr.add(pref, i);
    }

    cout << ans.second << " " << ans.first << "\n";
    return 0;
}

• Subtask 1: 0 / 100