#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> trie(1,{-1,-1});
vector<int> sm(1);
int x,ans = INT_MAX;
void ins(int p, int a, int d, int yo) {
if(d == -1) {
return;
}
if(a&(1 << d)) {
if(trie[p].second == -1) {
trie.push_back({-1,-1});
sm.push_back(yo);
trie[p] = {trie[p].first,trie.size()-1};
ins(trie.size()-1,a,d-1,yo);
}
else {
ins(trie[p].second,a,d-1,yo);
}
}
else {
if(trie[p].first == -1) {
trie.push_back({-1,-1});
sm.push_back(yo);
trie[p] = {trie.size()-1,trie[p].second};
ins(trie.size()-1,a,d-1,yo);
}
else {
ins(trie[p].first,a,d-1,yo);
}
}
}
void calc(int p, int a, int d) {
//cout << p << " " << d << " " << ans << endl;
if(d == -1) {
ans = min(ans,sm[p]);
return;
}
if(x&(1 << d)) {
if(a&(1 << d)) {
if(trie[p].first == -1) {
return;
}
calc(trie[p].first,a,d-1);
}
else {
if(trie[p].second == -1) {
return;
}
calc(trie[p].second,a,d-1);
}
}
else {
if(a&(1 << d)) {
if(trie[p].first != -1) {
ans = min(ans,sm[trie[p].first]);
}
if(trie[p].second != -1) {
calc(trie[p].second,a,d-1);
}
}
else {
if(trie[p].second != -1) {
ans = min(ans,sm[trie[p].second]);
}
if(trie[p].first != -1) {
calc(trie[p].first,a,d-1);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,l = -1,big = 0;
cin >> n >> x;
vector<int> haha(n+1);
for(int i = 1; i <= n; i++) {
cin >> haha[i];
haha[i]^=haha[i-1];
}
ins(0,0,30,0);
for(int i = 1; i <= n; i++) {
ans = INT_MAX;
calc(0,haha[i],30);
if(i-ans+1 > big) {
big = i-ans+1;
l = ans+1;
}
ins(0,haha[i],30,i);
}
cout << l << " " << big;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
