#include <bits/stdc++.h>
#define DIM 250010
using namespace std;
struct trie{
int poz; /// pozitia minima care ajunge prin nodul asta
trie *f[2];
trie (){
f[0] = f[1] = 0;
poz = 0;
}
};
trie *rad;
int v[DIM];
int n,i,sol,x;
void add_trie (trie *&rad, int val, int bit){
if (bit < 0)
return;
int nr = 0;
if (val & (1<<bit))
nr = 1;
if (rad->f[nr] == NULL){
rad->f[nr] = new trie();
rad->f[nr]->poz = i;
}
add_trie (rad->f[nr],val,bit-1);
}
void query (trie *&rad, int val, int x, int bit){
if (bit < 0)
return;
int p = 0;
if (val & (1<<bit))
p = 1;
if (x&(1<<bit)){ /// trb obligatoriu sa am 1
if (rad->f[p^1] != NULL)
query (rad->f[p^1],val,x,bit-1);
} else {
if (rad->f[p^1] != NULL)
sol = min (sol,rad->f[p^1]->poz);
if (rad->f[p] != NULL) /// ma duc tot in zero
query (rad->f[p],val,x,bit);
}
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>x;
for (i=1;i<=n;i++){
cin>>v[i];
v[i] ^= v[i-1];
}
if (n == 1){
cout<<"1 1";
return 0;
}
rad = new trie();
int ans = 1, poz = 1;
for (i=0;i<=n;i++){
if (i){
/// care e primul bit de 0 care difera?
sol = n+1;
query (rad,v[i],x,30);
if (i-sol > ans)
ans = i-sol, poz = sol+1;
}
add_trie (rad,v[i],30);
}
cout<<poz<<" "<<ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
