# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1074765 | nima_aryan | XOR (IZhO12_xor) | C++17 | 125 ms | 120604 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
struct S {
int k;
int i;
bool operator<(const S& other) const {
return pair{k, -i} < pair{other.k, -other.i};
}
};
constexpr int N = 1E7;
vector<array<int, 2>> trie(N);
vector<int> tag(N);
int tot = 1;
void insert(int x, int i) {
int p = 1;
for (int t = 31; t >= 0; --t) {
int& q = trie[p][x >> t & 1];
if (!q) {
q = ++tot;
}
p = q;
if (!tag[p]) {
tag[p] = i;
}
}
}
int get(int x, int v) {
int res = -1;
int p = 1;
for (int t = 31; t >= 0; --t) {
int bx = x >> t & 1;
int bv = v >> t & 1;
if (bv) {
p = trie[p][bx ^ 1];
} else {
res = max(res, tag[trie[p][bx ^ 1]]);
p = trie[p][bx];
}
if (!p) {
return res;
}
}
res = max(res, tag[p]);
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, x;
cin >> n >> x;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
S ans{0, 0};
insert(0, n);
for (int i = n - 1, s = 0; i >= 0; --i) {
s ^= a[i];
int j = get(s, x);
ans = max(ans, S{j - i, i});
insert(s, i);
}
cout << ans.i + 1 << " " << ans.k << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |