제출 #1327584

#제출 시각아이디문제언어결과실행 시간메모리
1327584trufanov.pXOR (IZhO12_xor)C++20
0 / 100
35 ms88344 KiB
#include "bits/stdc++.h"

using namespace std;

//const int SIZE = 100;
//const int MAXBIT = 3;

const int SIZE = 7500000;
const int MAXBIT = 29;
const int INF = 2e9;

struct TrieNode {
    int kids[2];
    int min_pref;
    TrieNode(int cur_val = -1) {
        kids[0] = kids[1] = -1;
        min_pref = cur_val;
    }
};

TrieNode nodes[SIZE];
int sz = 0;

int getNew(int cur_val = -1) {
    nodes[sz] = TrieNode(cur_val);
    return sz++;
}

int get_min(int v) {
    if (v == -1) {
        return INF;
    }
    return nodes[v].min_pref;
}

void add(int v, int x, int i, int cur_bit = MAXBIT) {
    if (cur_bit == -1) {
        nodes[v].min_pref = i;
        return;
    }
    int b = (x >> cur_bit) & 1;
    if (nodes[v].kids[b] == -1) {
        nodes[v].kids[b] = getNew();
    }
    add(nodes[v].kids[b], x, i, cur_bit - 1);
    nodes[v].min_pref = min(get_min(nodes[v].kids[0]), get_min(nodes[v].kids[1]));
}

int query(int v, int cur_xor, int x, int cur_bit = MAXBIT) {
    if (v == -1) {
        return INF;
    }
    if (cur_bit == -1) {
        return nodes[v].min_pref;
    }
    int xb = (x >> cur_bit) & 1;
    int cb = (cur_xor >> cur_bit) & 1;
    if (xb == 0) {
        if (cb == 0) {
            return min(get_min(nodes[v].kids[1]), query(nodes[v].kids[0], cur_xor, x, cur_bit - 1));
        } else {
            return min(get_min(nodes[v].kids[0]), query(nodes[v].kids[1], cur_xor, x, cur_bit - 1));
        }
    } else {
        if (cb == 0) {
            return query(nodes[v].kids[1], cur_xor, x, cur_bit - 1);
        } else {
            return query(nodes[v].kids[0], cur_xor, x, cur_bit - 1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, x;
    cin >> n >> x;
    int root = getNew();
    add(root, 0, -1);
    int cur_pref = 0;
    int max_len = 0;
    int start = -1;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        cur_pref ^= val;
        int cur_min = query(root, cur_pref, x) + 1;
        if (i - cur_min + 1 > max_len) {
            max_len = i - cur_min + 1;
            start = cur_min;
        }
        add(root, cur_pref, i);
    }
    cout << start + 1 << ' ' << max_len << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...