Submission #1268410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268410		iamarman	XOR (IZhO12_xor)	C++20	100 / 100	314 ms	57588 KiB

xor

#include<bits/stdc++.h>

using namespace std;


class TrieNode
{
public:
    TrieNode *left;
    TrieNode *right;
    int cnt;
    int ind;
    TrieNode()
    {
        left=NULL;
        right=NULL;
        cnt=0;
        ind=1e9;
    }
};

class Trie
{
    TrieNode *root;
public:

    Trie()
    {
        root=new TrieNode();
    }

    void insert(int n,int id)
    {
        TrieNode *curr=root;
        for(int i=31;i>=0;i--)
        {
            int bit=(1&(n>>i));
            if(bit==0)
            {
                if(curr->left==NULL)
                {
                    curr->left=new TrieNode();
                }
                curr=curr->left;
                curr->cnt++;
                curr->ind=min(curr->ind,id);
            }
            else
            {
                if(curr->right==NULL)
                {
                    curr->right=new TrieNode();
                }
                curr=curr->right;
                curr->cnt++;
                curr->ind=min(curr->ind,id);
            }
        }
    }

    void remove(int n) 
    {
        TrieNode* curr = root;

        for (int i = 31; i >= 0; i--) 
        {
            if(curr==NULL)
            {
                break;
            }
            
            int bit = (n >> i) & 1;

            if (bit == 0) 
            {
                curr = curr->left;
                curr->cnt--;
            } 
            else 
            {
                curr = curr->right;
                curr->cnt--;
            
            }
        }

    } 

    pair<int,int> max_xor_pair(int n)
    {
        TrieNode *curr=root;
        int ans=0;
        for(int i=31;i>=0;i--)
        {
            if(curr==NULL)
            {
                break;
            }
            int bit=(1&(n>>i));

            if(bit==0)
            {
                if(curr->right!=NULL and curr->right->cnt>0)
                {
                    ans+=(1<<i);
                    curr=curr->right;
                }
                else 
                {
                    curr=curr->left;
                }
            }
            else
            {
                if(curr->left!=NULL and curr->left->cnt>0)
                {
                    ans+=(1<<i);
                    curr=curr->left;
                }
                else
                {
                    curr=curr->right;
                }
            }
        }
        return {ans,curr->ind};
    }

    
};
void solve()
{
    int n,x;
    cin>>n>>x;
    vector<int> vec(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>vec[i];
        vec[i]^=vec[i-1];
    }

    Trie tr;
    tr.insert(0,0);
    int lenght=0;
    int start=0;
    for(int i=1;i<=n;i++)
    {
        auto cur=tr.max_xor_pair(vec[i]);
        if(cur.first>=x)
        {
            int len=i-cur.second;
            if(len>lenght)
            {
                start=cur.second;
                lenght=len;
            }
        }
        tr.insert(vec[i],i);
    }

    cout<<start+1<<" "<<lenght<<'\n';

}


int main()
{ 
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t=1;
   // cin>>t;
    for(int i=1;i<=t;i++)
    {
         //cout<<"Case "<<i<<": ";
        solve();
    }
}

• Subtask 1: 100 / 100