Submission #768237

#	Time	Username	Problem	Language	Result	Execution time	Memory
768237		Ahmed57	XOR (IZhO12_xor)	C++17	0 / 100	952 ms	262144 KiB

xor

#include<bits/stdc++.h>

using namespace std;
//TRIE
struct node{
   node *nxt[2];
   node(){
      for(int i = 0;i<2;i++){
        nxt[i] = NULL;
      }
   }
};
void inser(string w,node *root){
    for(auto ch:w){
        if(root->nxt[ch-'0']==NULL){
            root->nxt[ch-'0'] = new node();
        }
        root=root->nxt[ch-'0'];
    }
}
long long sear(string w,node *root){
    long long ans = 0 , val = 29;
    for(auto ch:w){
        if(ch=='0'){
            if(root->nxt[1]!=NULL){
                root = root->nxt[1];
                ans+=(1<<val);
            }else{
                root = root->nxt[0];
            }
        }else{
            if(root->nxt[0]!=NULL){
                root = root->nxt[0];
                ans+=(1<<val);
            }else{
                root = root->nxt[1];
            }
        }
        val--;
    }
    return ans;
}
int main(){
    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 l = 1, r = n , lolo = 0 , an = 0;
    while(l<=r){
        long long mid = (l+r)/2;
        node *root = new node();
        bool ss = 0;
        int lelo =-1;
        for(int i = n-mid;i>=0;i--){
            string s;
            for(int j = 29;j>=0;j--){
                if(arr[i+mid]&(1<<j)){
                    s+='1';
                }else s+='0';
            }
            inser(s,root);
            string v;
            for(int j = 29;j>=0;j--){
                if(arr[i]&(1<<j)){
                    v+='1';
                }else v+='0';
            }
            long long val = sear(v,root);
            if(val>=x){
                ss = 1;
                lelo = i;
            }
        }
        if(ss){
            an = mid;
            lolo = lelo;
            l = mid+1;
        }else r = mid-1;
        delete(root);
    }
    cout<<lolo+1<<" "<<an<<endl;
}

• Subtask 1: 0 / 100