Submission #768254

#	Time	Username	Problem	Language	Result	Execution time	Memory
768254		Ahmed57	XOR (IZhO12_xor)	C++17	100 / 100	316 ms	60440 KiB

xor

#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;
}

• Subtask 1: 100 / 100