# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
589140 |
2022-07-04T09:39:00 Z |
Mamedov |
XOR (IZhO12_xor) |
C++17 |
|
320 ms |
143784 KB |
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Trie {
int val;
vector<Trie*>link;
Trie(int v): val(v), link(vector<Trie*>(2, nullptr)) {}
void add(int num, int id) {
Trie *node = this;
for (int i = 30; i >= 0; --i) {
int bit = ((num >> i) & 1);
if (node->link[bit]) {
node = node->link[bit];
node->val = id;
} else {
node = node->link[bit] = new Trie(id);
}
}
}
int findBestr(int l, int x) {
Trie *node = this;
int bestr = -1;
for (int i = 30; i >= 0; --i) {
int bitl = ((l >> i) & 1);
int bitx = ((x >> i) & 1);
if (bitx) {
if (node->link[bitl ^ 1]) {
node = node->link[bitl ^ 1];
} else {
return bestr;
}
} else {
if (node->link[bitl ^ 1]) {
bestr = max(bestr, node->link[bitl ^ 1]->val);
}
if (node->link[bitl]) {
if (node->link[bitl]->val > bestr) {
node = node->link[bitl];
} else {
return bestr;
}
}
}
}
bestr = max(bestr, node->val);
return bestr;
}
};
void solve() {
int n, x;
cin >> n >> x;
vector<int>p(n + 1);
p[0] = 0;
Trie *root = new Trie(0);
for (int i = 1; i <= n; ++i) {
cin >> p[i];
p[i] ^= p[i - 1];
root->add(p[i], i);
}
int l = 0, len = 0;
for (int i = 0; i < n; ++i) {
int bestr = root->findBestr(p[i], x);
if (bestr - i > len) {
len = bestr - i;
l = i + 1;
}
}
cout << l << ' ' << len << ln;
}
int main() {
ios_base::sync_with_stdio(false);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
448 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
11 ms |
3908 KB |
Output is correct |
6 |
Correct |
16 ms |
4428 KB |
Output is correct |
7 |
Correct |
15 ms |
4408 KB |
Output is correct |
8 |
Correct |
20 ms |
4584 KB |
Output is correct |
9 |
Correct |
132 ms |
67504 KB |
Output is correct |
10 |
Correct |
129 ms |
67876 KB |
Output is correct |
11 |
Correct |
125 ms |
67460 KB |
Output is correct |
12 |
Correct |
124 ms |
67628 KB |
Output is correct |
13 |
Correct |
123 ms |
67784 KB |
Output is correct |
14 |
Correct |
121 ms |
67864 KB |
Output is correct |
15 |
Correct |
128 ms |
67868 KB |
Output is correct |
16 |
Correct |
129 ms |
67700 KB |
Output is correct |
17 |
Correct |
320 ms |
143496 KB |
Output is correct |
18 |
Correct |
309 ms |
143784 KB |
Output is correct |
19 |
Correct |
292 ms |
143696 KB |
Output is correct |
20 |
Correct |
314 ms |
143608 KB |
Output is correct |