#include <iostream>
using namespace std;
const int N = 2e5 + 10;
const int LG = 30;
int n, x, a[N];
struct Trie {
struct node {
node *child[2];
node () {
child[0] = child[1] = nullptr;
}
};
node *root;
Trie () {root = new node();}
void DFS(node *cur) {
for (int i = 0; i <= 1; ++i) {
if (cur->child[i]) DFS(cur->child[i]);
}
delete(cur);
}
void reset() {
DFS(root);
root = new node();
}
void add(int u) {
node *cur = root;
for (int i = LG; i >= 0; --i) {
int c = u >> i & 1;
if (!cur->child[c]) cur->child[c] = new node();
cur = cur->child[c];
}
}
int Max(int u) {
int res = 0;
node *cur = root;
for (int i = LG; i >= 0; --i) {
int c = u >> i & 1;
if (cur->child[c ^ 1]) {
res |= (1 << i);
cur = cur->child[c ^ 1];
} else {
cur = cur->child[c];
}
}
return res;
}
} T;
int check(int val) {
int mx = 0, I = 0;
for (int i = n - val + 1; i >= 1; --i) {
T.add(a[i + val]);
int cur = T.Max(a[i]);
if (cur > mx) {
mx = cur;
I = i;
}
}
T.reset();
if (mx >= x) return I;
return 0;
}
int main() {
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> x;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = n; i >= 1; --i) a[i] ^= a[i + 1];
int l = 1, r = n, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (ans == -1) cout << ans << "\n";
else {
cout << check(ans) << " ";
cout << ans << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |