// #pragma GCC optimize("Ofast,O3")
// #pragma GCC target("avx,avx2")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
void solve() {
int n, c;
cin >> n >> c;
vector<int> a(n + 1), pref(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] ^ a[i];
pair<int, int> ans = make_pair(0, 0);
auto upd = [&](int l, int r) -> void {
if (ans.second > r - l + 1) return;
if (ans.second < r - l + 1) ans = make_pair(l, r - l + 1);
else ans.first = min(ans.first, l);
};
vector<map<int, int>> have(30);
for (int i = 0; i < 30; i++) have[i][0] = 0;
for (int i = 1; i <= n; i++) {
// pref[i] ^ pref[x] >= c
int now = 0, j = 29;
for (; j >= 0; j--) {
if (c & (1 << j)) {
now |= (pref[i] & (1 << j) ? 0 : 1 << j);
if (!have[j].count(now)) break;
} else {
if (pref[i] & (1 << j)) {
if (have[j].count(now)) {
upd(have[j][now] + 1, i);
break;
}
now |= 1 << j;
assert(have[j][now]);
continue;
}
if (have[j].count(now | (1 << j))) {
upd(have[j][now | (1 << j)] + 1, i);
break;
}
}
}
if (j < 0) upd(have[0][now] + 1, i);
now = 0;
for (j = 29; j >= 0; j--) {
now |= pref[i] & (1 << j);
if (!have[j][now]) have[j][now] = i;
}
}
cout << ans.first << ' ' << ans.second;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int q = 1;
// cin >> q;
while (q--) {
solve();
cout << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
604 KB |
Output is correct |
5 |
Correct |
25 ms |
2652 KB |
Output is correct |
6 |
Correct |
32 ms |
2928 KB |
Output is correct |
7 |
Correct |
33 ms |
3132 KB |
Output is correct |
8 |
Correct |
35 ms |
3080 KB |
Output is correct |
9 |
Correct |
386 ms |
41556 KB |
Output is correct |
10 |
Correct |
386 ms |
42088 KB |
Output is correct |
11 |
Correct |
380 ms |
41556 KB |
Output is correct |
12 |
Correct |
393 ms |
41820 KB |
Output is correct |
13 |
Correct |
376 ms |
41808 KB |
Output is correct |
14 |
Correct |
397 ms |
41876 KB |
Output is correct |
15 |
Correct |
386 ms |
41800 KB |
Output is correct |
16 |
Correct |
389 ms |
42060 KB |
Output is correct |
17 |
Correct |
1117 ms |
88652 KB |
Output is correct |
18 |
Correct |
1119 ms |
88976 KB |
Output is correct |
19 |
Correct |
1151 ms |
88688 KB |
Output is correct |
20 |
Correct |
1151 ms |
88732 KB |
Output is correct |