# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
768254 |
2023-06-27T19:55:19 Z |
Ahmed57 |
XOR (IZhO12_xor) |
C++17 |
|
316 ms |
60440 KB |
#include<bits/stdc++.h>
using namespace std;
//TRIE
struct node{
node *nxt[2];
int ind;
node(){
ind = -1;
for(int i = 0;i<2;i++){
nxt[i] = NULL;
}
}
};
void inser(string w,int in,node *root){
for(auto ch:w){
if(root->nxt[ch-'0']==NULL){
root->nxt[ch-'0'] = new node();
}
root=root->nxt[ch-'0'];
root->ind = max(root->ind,in);
}
}
int sear(string w,int ind,long long y,node *root){
int ans = -1 , val = 29-ind;
if(w[ind]=='0'){
if(root->nxt[1]!=NULL){
if(y<=(1<<val)){
ans = max(ans,root->nxt[1]->ind);
}else{
ans = max(ans,sear(w,ind+1,y-(1<<val),root->nxt[1]));
}
}if(root->nxt[0]!=NULL&&y<(1<<val)){
ans = max(ans,sear(w,ind+1,y,root->nxt[0]));
}
}else{
if(root->nxt[0]!=NULL){
if(y<=(1<<val)){
ans = max(ans,root->nxt[0]->ind);
}else{
ans = max(ans,sear(w,ind+1,y-(1<<val),root->nxt[0]));
}
}if(root->nxt[1]!=NULL&&y<(1<<val)){
ans = max(ans,sear(w,ind+1,y,root->nxt[1]));
}
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
long long n,x;
cin>>n>>x;
long long arr[n+1] = {0};
for(int i = 0;i<n;i++)cin>>arr[i];
for(int i = n-1;i>=0;i--)arr[i]^=arr[i+1];
long long an = 0 ,lolo = 0;
node *root = new node();
for(int i = n-1;i>=0;i--){
string s;
for(int j = 29;j>=0;j--){
if(arr[i+1]&(1<<j)){
s+='1';
}else s+='0';
}
inser(s,i+1,root);
s = "";
for(int j = 29;j>=0;j--){
if(arr[i]&(1<<j)){
s+='1';
}else s+='0';
}
int xd = sear(s,0,x,root);
if(xd-i>=an){
an = xd-i;
lolo = i;
}
}
cout<<lolo+1<<" "<<an<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
23 ms |
1884 KB |
Output is correct |
6 |
Correct |
31 ms |
2196 KB |
Output is correct |
7 |
Correct |
31 ms |
2144 KB |
Output is correct |
8 |
Correct |
34 ms |
2336 KB |
Output is correct |
9 |
Correct |
118 ms |
27804 KB |
Output is correct |
10 |
Correct |
125 ms |
28452 KB |
Output is correct |
11 |
Correct |
112 ms |
28244 KB |
Output is correct |
12 |
Correct |
115 ms |
28280 KB |
Output is correct |
13 |
Correct |
113 ms |
28320 KB |
Output is correct |
14 |
Correct |
114 ms |
28412 KB |
Output is correct |
15 |
Correct |
122 ms |
28396 KB |
Output is correct |
16 |
Correct |
114 ms |
28364 KB |
Output is correct |
17 |
Correct |
301 ms |
60376 KB |
Output is correct |
18 |
Correct |
316 ms |
60364 KB |
Output is correct |
19 |
Correct |
302 ms |
60440 KB |
Output is correct |
20 |
Correct |
298 ms |
60380 KB |
Output is correct |