# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
898665 |
2024-01-05T01:37:44 Z |
typ_ik |
XOR (IZhO12_xor) |
C++17 |
|
212 ms |
87648 KB |
#include <bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 3e5 + 128;
const int LOG = 31;
int n, x;
int a[N];
struct node {
node* nxt[2];
int min_id;
node* p;
node() {
nxt[0] = nxt[1] = p = nullptr;
min_id = N;
}
void upd() {
if (nxt[0] != nullptr)
min_id = min(min_id, nxt[0]->min_id);
if (nxt[1] != nullptr)
min_id = min(min_id, nxt[1]->min_id);
}
};
node* root = new node();
void add(int val, int pos) {
node* cur = root;
for (int b = LOG - 1; b >= 0; b--) {
bool v = ((val >> b) & 1);
if (cur->nxt[v] == nullptr)
cur->nxt[v] = new node(), cur->nxt[v]->p = cur;
cur = cur->nxt[v];
}
cur->min_id = min(cur->min_id, pos);
while (cur != nullptr)
cur->upd(), cur = cur->p;
}
int get(int val) {
node* cur = root;
int ans = N;
for (int b = LOG - 1; b >= 0 && cur != nullptr; b--) {
bool v = ((x >> b) & 1);
bool have = ((val >> b) & 1);
if (!v && cur->nxt[have ^ 1] != nullptr)
ans = min(ans, cur->nxt[have ^ 1]->min_id);
cur = cur->nxt[have ^ v];
}
if (cur != nullptr)
ans = min(ans, cur->min_id);
return ans;
}
void solve() {
cin >> n >> x;
for (int i = 1; i <= n; i++)
cin >> a[i], a[i] ^= a[i - 1];
add(0, 0);
int L = 0, R = -1;
for (int i = 1; i <= n; i++) {
add(a[i], i);
int nl = get(a[i]);
if (i - nl > R - L)
L = nl, R = i;
}
cout << L + 1 << ' ' << R - L << '\n';
}
main() {
boost;
solve();
return 0;
}
Compilation message
xor.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
89 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
8 ms |
2652 KB |
Output is correct |
6 |
Correct |
10 ms |
2904 KB |
Output is correct |
7 |
Correct |
10 ms |
3060 KB |
Output is correct |
8 |
Correct |
12 ms |
3420 KB |
Output is correct |
9 |
Correct |
73 ms |
41292 KB |
Output is correct |
10 |
Correct |
75 ms |
41296 KB |
Output is correct |
11 |
Correct |
75 ms |
41040 KB |
Output is correct |
12 |
Correct |
79 ms |
41296 KB |
Output is correct |
13 |
Correct |
79 ms |
41296 KB |
Output is correct |
14 |
Correct |
75 ms |
41304 KB |
Output is correct |
15 |
Correct |
71 ms |
41300 KB |
Output is correct |
16 |
Correct |
71 ms |
41344 KB |
Output is correct |
17 |
Correct |
212 ms |
87636 KB |
Output is correct |
18 |
Correct |
195 ms |
87632 KB |
Output is correct |
19 |
Correct |
210 ms |
87648 KB |
Output is correct |
20 |
Correct |
205 ms |
87484 KB |
Output is correct |