#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;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |