#include <bits/stdc++.h>
using namespace std;
const int N = (int)250000 + 7;
const int inf = (int)1e9 + 7;
int n, X;
int pref[N], a[N];
struct st {
int to[2], pr, val;
st() {
to[0] = to[1] = 0;
pr = 0;
val = inf;
}
};
st bor[N * 60];
int siz = 1;
void add(int x, int pos) {
int v = 1;
for (int i = 30; i >= 0; i--) {
if (!bor[v].to[(x >> i) & 1]) {
bor[v].to[(x >> i) & 1] = ++siz;
bor[bor[v].to[(x >> i) & 1]].pr = v;
}
v = bor[v].to[(x >> i) & 1];
}
bor[v].val = min(pos, bor[v].val);
v = bor[v].pr;
while (v > 0) {
int res = inf;
if (bor[v].to[0]) {
res = min(res, bor[bor[v].to[0]].val);
}
if (bor[v].to[1]) {
res = min(res, bor[bor[v].to[1]].val);
}
bor[v].val = min(bor[v].val, res);
v = bor[v].pr;
}
}
int get(int x) {
int res = inf;
int v = 1;
for (int i = 30; i >= 0 && v > 0; i--) {
int tto = (x >> i) & 1;
if ((X >> i) & 1 ^ 1) {
if (bor[v].to[tto ^ 1]) {
res = min(res, bor[bor[v].to[tto ^ 1]].val);
}
v = bor[v].to[tto];
} else {
if (tto)
v = bor[v].to[0];
else
v = bor[v].to[1];
}
}
res = min(res, bor[v].val);
return res;
}
main() {
//freopen("c.in", "r", stdin);
//freopen("c.out", "w", stdout);
scanf("%d %d", &n, &X);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
pref[i] = pref[i - 1] ^ a[i];
}
pair < int, int > ans;
ans = {0, 0};
add(0, 0);
for (int i = 1; i <= n; i++) {
int asd = get(pref[i]);
//cout << asd << ' ' << endl;
int len = i - asd;
if (len > ans.second) {
ans.second = len;
ans.first = i - len + 1;
}
add(pref[i], i);
}
printf("%d %d\n", ans.first, ans.second);
}
Compilation message
xor.cpp: In function 'int get(int)':
xor.cpp:51:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
if ((X >> i) & 1 ^ 1) {
~~~~~~~~~^~~
xor.cpp: At global scope:
xor.cpp:67:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
xor.cpp: In function 'int main()':
xor.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &X);
~~~~~^~~~~~~~~~~~~~~~~
xor.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
235272 KB |
Output is correct |
| 2 |
Correct |
217 ms |
235272 KB |
Output is correct |
| 3 |
Correct |
217 ms |
235508 KB |
Output is correct |
| 4 |
Correct |
189 ms |
235508 KB |
Output is correct |
| 5 |
Correct |
210 ms |
235836 KB |
Output is correct |
| 6 |
Correct |
213 ms |
236108 KB |
Output is correct |
| 7 |
Correct |
234 ms |
236240 KB |
Output is correct |
| 8 |
Correct |
211 ms |
236456 KB |
Output is correct |
| 9 |
Correct |
266 ms |
237800 KB |
Output is correct |
| 10 |
Correct |
302 ms |
238564 KB |
Output is correct |
| 11 |
Correct |
293 ms |
239368 KB |
Output is correct |
| 12 |
Correct |
294 ms |
240156 KB |
Output is correct |
| 13 |
Correct |
278 ms |
240960 KB |
Output is correct |
| 14 |
Correct |
297 ms |
241564 KB |
Output is correct |
| 15 |
Correct |
289 ms |
242620 KB |
Output is correct |
| 16 |
Correct |
293 ms |
243236 KB |
Output is correct |
| 17 |
Correct |
456 ms |
246428 KB |
Output is correct |
| 18 |
Correct |
468 ms |
248292 KB |
Output is correct |
| 19 |
Correct |
468 ms |
250248 KB |
Output is correct |
| 20 |
Correct |
476 ms |
252036 KB |
Output is correct |
