| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1352718 | vjudge1 | XOR (IZhO12_xor) | C11 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int N = 29;
struct node
{
int child[2];
int id;
node()
{
child[0] = child[1] = -1;
id = 1e9;
}
};
vector<node> trie;
void insert(int val, int idx)
{
int cnt = 0;
trie[cnt].id = min(trie[cnt].id, idx);
for (int b = N; b >= 0; --b)
{
int bit = (val >> b) & 1;
if (trie[cnt].child[bit] == -1)
{
trie[cnt].child[bit] = trie.size();
trie.emplace_back();
}
cnt = trie[cnt].child[bit];
trie[cnt].id = min(trie[cnt].id, idx);
}
}
int query(int pj, int x)
{
int cnt = 0;
int res = 1e9;
for (int b = N; b >= 0; --b)
{
if (cnt == -1) break;
int b1 = (pj >> b) & 1;
int b2 = (x >> b) & 1;
if (b2 == 0)
{
int x1 = trie[cnt].child[1 - b1];
if (x1 != -1)
{
res = min(res, trie[x1].id);
}
cnt = trie[cnt].child[b1];
}
else
{
cnt = trie[cnt].child[1 - b1];
}
}
if (cnt != -1)
{
res = min(res, trie[cnt].id);
}
return res;
}
int main()
{
int n, x;
cin >> n >> x;
trie.emplace_back();
insert(0, 0);
int pre = 0;
int best = -1, max1 = -1;
for (int j = 1; j <= n; ++j)
{
int a;
cin >> a;
pre ^= a;
int min1 = query(pre, x);
if (min1 != 1e9) {
int k = j - min1;
int i = min1 + 1;
if (k > max1)
{
max1 = k;
best = i;
}
else if (k == max1)
{
best = min(best, i);
}
}
insert(pre, j);
}
if (best != -1)
{
cout << best << " " << max1 ;
}
}