# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
446571 |
2021-07-22T13:05:42 Z |
minaie_mehrzad |
XOR (IZhO12_xor) |
C++14 |
|
492 ms |
153796 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 25e4 + 10, lg = 31;
int n, a[maxn], z;
struct node {
node *rc, *lc;
int mn;
node () {
lc = nullptr;
rc = nullptr;
mn = 1e9;
}
node * getChild(int x) {
if (x) {
if (rc == nullptr) rc = new node();
return rc;
} else {
if (lc == nullptr) lc = new node();
return lc;
}
}
};
struct Trie {
node *root;
Trie () {
root = new node();
}
void add(int x, int y) {
node * cur = root;
for (int i = lg; i >= 0; i--) {
cur = cur->getChild(!!((1 << i) & x));
cur->mn = min(cur->mn, y);
}
}
} T;
int solve(int x) {
int ans = 1e9;
node *cur = T.root;
for (int i = lg; i >= 0; i--) {
int c = !!((1 << i) & x), d = !!((1 << i) & z);
if (!d) {
ans = min(ans, cur->getChild(!c)->mn);
}
cur = cur->getChild(c ^ d);
}
ans = min(ans, cur->mn);
return ans;
}
int main () {
ios_base::sync_with_stdio(false);
cin >> n >> z;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] ^= a[i-1];
T.add(a[i], i);
}
int ans = 0, ind = 0;
for (int i = 1; i <= n; i++) {
if (a[i] >= z && ans < i) {
ans = i;
ind = 1;
}
int r = solve(a[i]);
if (ans < i - r) {
ans = i - r;
ind = r + 1;
}
}
cout << ind << " " << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
844 KB |
Output is correct |
5 |
Correct |
14 ms |
3252 KB |
Output is correct |
6 |
Correct |
17 ms |
3840 KB |
Output is correct |
7 |
Correct |
18 ms |
3612 KB |
Output is correct |
8 |
Correct |
19 ms |
3788 KB |
Output is correct |
9 |
Correct |
187 ms |
64580 KB |
Output is correct |
10 |
Correct |
172 ms |
66500 KB |
Output is correct |
11 |
Correct |
170 ms |
62712 KB |
Output is correct |
12 |
Correct |
166 ms |
62276 KB |
Output is correct |
13 |
Correct |
157 ms |
59860 KB |
Output is correct |
14 |
Correct |
163 ms |
60780 KB |
Output is correct |
15 |
Correct |
178 ms |
71576 KB |
Output is correct |
16 |
Correct |
161 ms |
60484 KB |
Output is correct |
17 |
Correct |
442 ms |
146136 KB |
Output is correct |
18 |
Correct |
440 ms |
144420 KB |
Output is correct |
19 |
Correct |
492 ms |
153796 KB |
Output is correct |
20 |
Correct |
413 ms |
131392 KB |
Output is correct |