#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i<(n); i++)
#define f1(i, n) for(int i(1); i<=(n); i++)
#define bit(tu, ut) (((tu) >> (ut))&1)
#define F(tr) ((tr%2))
using namespace std;
typedef long long ll;
const int N = 250002;
int n, a[N], f[N][31], d[N][30], x;
map <pair <int, int>, int> Map;
map <int, int> pam;
int main(){
ios_base::sync_with_stdio(0);
memset(f, 0, sizeof(f));
cin >> n >> x;
f1(i, n) cin >> a[i];
f1(i, n){
for(int j = 0; j <= 30; j++){
int bit = (a[i] >> j)&1;
f[i][j] = f[i - 1][j] + bit;
}
}
for(int i = n; i >= 1; i--){
int val = 0;
for(int j = 30; j >= 0; j--){
if(f[i][j]%2==1) val += (1 << j);
if(Map[make_pair(val, j)]==0) Map[make_pair(val, j)] = i;
}
if(pam[val]==0) pam[val] = i;
}
if(x==0){
cout << 1 << " " << n;
return 0;
}
for(int i = 1; i <= n; i++){
f0(j, 30){
if(bit(a[i], j)){
d[i][j] = i;
}
else{
d[i][j] = d[i - 1][j];
}
}
}
int kbit = -1;
for(int j = 30; j >= 0; j--) if(bit(x, j)){
kbit = j;
break;
}
int pos = -1, len = 0;
f1(i, n){
for(int j = 30; j > kbit; j--){
/// khac bit tu bit thu j
int dbit = f[n][j] - f[i - 1][j];
if(dbit){
int g = d[n][j];
if(dbit%2==0) g = d[g - 1][j];
/// i -> g
if((g - i + 1) > len){
len = (g - i + 1);
pos = i;
}
}
}
for(int j = kbit; j > 0; j--){
if(bit(x, j - 1)==0){
/// giong nhau den bit thu j va khac nhau o bit j - 1
x += (1 << (j - 1));
int val = 0;
for(int k = kbit; k >= j - 1; k--){
if(bit(x, k)==0){
if(F(f[i - 1][k])==1) val += (1 << k);
}
else{
if(F(f[i - 1][k])==0) val += (1 << k);
}
}
x -= (1 << (j - 1));
int sop = Map[make_pair(val, j - 1)];
if(sop){
if((sop - i + 1) > len){
len = (sop - i + 1);
pos = i;
}
}
}
}
}
/// now solve = x
f1(i, n){
int val = 0;
for(int k = kbit; k >= 0; k--){
if(bit(x, k)==0){
if(F(f[i - 1][k])==1) val += (1 << k);
}
else{
if(F(f[i - 1][k])==0) val += (1 << k);
}
}
int sop = pam[val];
if((sop - i + 1) > len){
len = (sop - i + 1);
pos = i;
}
}
cout << pos << " " << len;
/*pos = 0, len = 0;
f1(i, n){
int val = 0;
for(int j = i; j <= n; j++){
val ^= a[j];
if(val >= x){
if((j - i + 1) > len){
len = (j - i + 1);
pos = i;
}
}
}
}
cout << endl << pos << " " << len;
int u = 0;
f1(i, n) u ^= a[i];
cout << endl << u;
*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
30712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
