Submission #1268256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268256		iamarman	XOR (IZhO12_xor)	C++20	0 / 100	787 ms	327680 KiB

xor

#include<bits/stdc++.h>

using namespace std;





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

class Trie
{
    TrieNode *root;
public:
    Trie()
    {
        root = new TrieNode();
    }

    void insert(int n)
    {
        TrieNode *curr = root;
        // use bits 30..0 (safe for inputs <= 1e9)
        for (int i = 30; i >= 0; --i)
        {
            int bit = (n >> i) & 1;
            if (bit == 0)
            {
                if (curr->left == NULL)
                    curr->left = new TrieNode();
                curr = curr->left;
                curr->cnt++;
            }
            else
            {
                if (curr->right == NULL)
                    curr->right = new TrieNode();
                curr = curr->right;
                curr->cnt++;
            }
        }
    }

    int max_xor_pair(int n)
    {
        TrieNode *curr = root;
        int ans = 0;
        for (int i = 30; i >= 0; --i)
        {
            if (curr == NULL) break;
            int bit = (n >> i) & 1;
            if (bit == 0)
            {
                if (curr->right != NULL && curr->right->cnt > 0)
                {
                    ans |= (1 << i);   // safe shift because i <= 30
                    curr = curr->right;
                }
                else
                {
                    curr = curr->left;
                }
            }
            else
            {
                if (curr->left != NULL && curr->left->cnt > 0)
                {
                    ans |= (1 << i);
                    curr = curr->left;
                }
                else
                {
                    curr = curr->right;
                }
            }
        }
        return ans;
    }
};

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

    auto ok=[&](int len)->bool
    {
        Trie tr;
        tr.insert(0);
        for(int i=len;i<=n;i++)
        {
            tr.insert(vec[i-len]);
            if(tr.max_xor_pair(vec[i])>=x) return true;
        }
        return false;
    };

    int low=1,high=n+1;
    while(high-low>1)
    {
        int mid=low+(high-low)/2;
        if(ok(mid)) low=mid;
        else high=mid;
    }

    Trie tr;
    tr.insert(0);
    for(int i=low;i<=n;i++)
    {
        tr.insert(vec[i-low]);
        if(tr.max_xor_pair(vec[i])>=x)
        {
            cout<<i-low+1<<" "<<low<<'\n';
            return;
        }   
    }

}
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: 0 / 100