| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1224732 | Kerim | XOR (IZhO12_xor) | C11 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
#define ll long long
using namespace std;
const int N = 250005;
const int LOG = 30;
int id, tree[N*LOG][2], sub[N*LOG];
int p[N];
void add(int x, int ind){
int cur_node = 0;
for (int i = LOG-1; i >= 0; i--){
int bit = (x>>i&1);
if (!tree[cur_node][bit])
tree[cur_node][bit] = ++id;
cur_node = tree[cur_node][bit];
sub[cur_node] = ind;
}
}
// b^value >= a
//p[r]^p[l-1]>=x
int query(int a, int b){
int cur_node = 0;
int answer = 1e9;
for (int i = LOG-1; i >= 0; i--){
int a_bit = (a>>i&1);
int b_bit = (b>>i&1);
int to_node = 0;
for (int v_bit = 0; v_bit < 2; v_bit += 1){
if (!tree[cur_node][v_bit])
continue;
if ((b_bit ^ v_bit) > a_bit)
answer = min(answer, sub[tree[cur_node][v_bit]]);
else if((b_bit ^ v_bit) == a_bit)
to_node = tree[cur_node][v_bit];
}
if (!to_node)
return answer;
cur_node = to_node;
}
// b^value=a
return min(answer, sub[cur_node]);
}
int main(){
// freopen("file.in", "r", stdin);
int n, x;
scanf("%d%d", &n, &x);
for (int i = 1; i <= n; i++){
int x;
scanf("%d", &x);
p[i] = p[i-1]^x;
}
int k = 0, ind;
//p[r]^p[l-1]>=x
//p[r]^value>=x, minimum(index)
//add(p[l-1], l) = add(value, index);
for (int r = 1; r <= n; r++){
add(p[r-1], r);//r=l
int l = query(x, p[r]);
if (l <= r){
if (r-l+1 > k)
k = r-l+1, ind = l;
else if(r-l+1 == k)
ind = min(ind, l);
}
}
printf("%d %d\n", ind, k);
}