# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
966137 |
2024-04-19T12:18:34 Z |
dosts |
XOR (IZhO12_xor) |
C++17 |
|
6 ms |
1164 KB |
//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define vi vector<int>
const int N = 2e5+100,inf = INT_MAX,MOD = 1e9+7,LIM = 3e7+1;
int curnode = 1;
struct Node {
int c[2],mx;
};
Node nds[LIM];
int walk(Node* cur, int x,int k,int bit = 29) {
if (bit == -1) return k?0:cur->mx;
//x ile xor layınca en az k gelmesi lzm
if (k & (1<<bit)) {
int go = !(x&(1<<bit));
if (cur->c[go]) return walk(nds+cur->c[go],x,k^(1<<bit),bit-1);
else return 0;
}
else {
int go = !(x&(1<<bit));
int ans = 0;
if (cur->c[go]) ans = max(ans,nds[cur->c[go]].mx);
ans = max(ans,walk(nds+cur->c[!go],x,k,bit-1));
return ans;
}
}
void insert(int x,int p) {
Node* cur = nds+1;
for (int i=29;i>=-1;i--) {
cur->mx = max(cur->mx,p);
if (i > -1) {
bool go = !!(x&(1<<i));
if (!cur->c[go]) cur->c[go] = ++curnode;
cur = nds+cur->c[go];
}
}
}
void solve() {
int n,x;
cin >> n >> x;
vi a(n+1),p(n+1,0);
for (int i=1;i<=n;i++) cin >> a[i];
for (int i=1;i<=n;i++) p[i] = p[i-1]^a[i];
int ans = 0,start = 0;
for (int i=n;i>=1;i--) {
insert(p[i],i);
int xx = walk(nds+1,p[i-1],x);
if (xx-i+1 > ans) {
ans = xx-i+1;
start = i;
}
}
cout << start sp ans << endl;
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
756 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Incorrect |
6 ms |
1164 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |