# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
902498 | LCJLY | XOR (IZhO12_xor) | C++14 | 0 ms | 348 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;
struct trie{
trie *next[2];
int left=INT_MAX;
trie(){
next[0]=next[1]=NULL;
}
};
auto root=new trie();
void solve(){
int n,k;
cin >> n >> k;
int arr[n];
for(int x=0;x<n;x++){
cin >> arr[x];
}
int hold=0;
int best=-1;
int index=-1;
for(int x=0;x<n;x++){
hold^=arr[x];
auto cur=root;
//query
for(int y=30;y>=0;y--){
if(k&(1<<y)){
bool amos=(hold&(1<<y));
if(cur->next[amos]==NULL)cur->next[amos]=new trie();
cur=cur->next[amos];
if(x-cur->left>best){
best=x-cur->left;
index=x+1;
}
}
else{
bool amos=(hold&(1<<y));
if(cur->next[amos]==NULL)cur->next[amos]=new trie();
cur=cur->next[amos];
if(x-cur->left>best){
best=x-cur->left;
index=x+1;
}
}
}
//add
cur=root;
for(int y=30;y>=0;y--){
bool amos=(hold&(1<<y));
if(cur->next[amos]==NULL)cur->next[amos]=new trie();
cur=cur->next[amos];
cur->left=min(cur->left,x);
}
}
cout << index-best+1 << " " << best;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |