제출 #1318867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318867		kero	XOR (IZhO12_xor)	C++20	100 / 100	120 ms	58480 KiB

xor

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

struct Node {
    Node* child[2];
    int minIdx;
    Node() {
        child[0] = child[1] = nullptr;
        minIdx = INT_MAX;
    }
};

void insert(Node* root, int val, int idx) {
    Node* cur = root;
    for (int b = 30; b >= 0; b--) {
        int bit = (val >> b) & 1;
        if (!cur->child[bit])
            cur->child[bit] = new Node();
        cur = cur->child[bit];
        cur->minIdx = min(cur->minIdx, idx);
    }
}

int query(Node* root, int val, int x) {
    Node* cur = root;
    int res = INT_MAX;

    for (int b = 30; b >= 0; b--) {
        if (!cur) break;

        int vb = (val >> b) & 1;
        int xb = (x >> b) & 1;

        if (xb == 0) {
            if (cur->child[1 - vb])
                res = min(res, cur->child[1 - vb]->minIdx);
            cur = cur->child[vb];
        } else {
            cur = cur->child[1 - vb];
        }
    }
    if (cur)
        res = min(res, cur->minIdx);

    return res;
}

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

    int N;
    int x;
    cin >> N >> x;

    vector<int> a(N + 1), pref(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        pref[i] = pref[i - 1] ^ a[i];
    }

    Node* root = new Node();
    insert(root, 0, 0);

    int bestLen = 0;
    int bestL = 1;

    for (int r = 1; r <= N; r++) {
        int j = query(root, pref[r], x);
        if (j != INT_MAX) {
            int len = r - j;
            if (len > bestLen) {
                bestLen = len;
                bestL = j + 1;
            }
        }
        insert(root, pref[r], r);
    }

    cout << bestL << " " << bestLen << "\n";
    return 0;
}

• Subtask 1: 100 / 100