Description

Submission

class Solution {
    struct TrieNode {
        TrieNode* next[2];
    };
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        int n = queries.size();
        for(int i = 0; i < n; ++i) {
            queries[i].push_back(i);
        }

        sort(nums.begin(), nums.end());
        sort(queries.begin(), queries.end(), [](auto& v1, auto&v2) {
            return v1[1] < v2[1];
        });

        vector<int> rets(n);

        TrieNode* trie = new TrieNode();
        int k = 0;
        for(auto& q: queries) {
            for(; k < nums.size() && nums[k] <= q[1]; ++k) {
                TrieNode* p = trie;
                for(int i = 31; i >= 0; --i) {
                    if(!p->next[(nums[k]>>i)&1]) {
                        p->next[(nums[k]>>i)&1] = new TrieNode();
                    }
                    p = p->next[(nums[k]>>i)&1];
                }
            }

            if(k == 0) {
                rets[q[2]] = -1;
                continue;
            }

            TrieNode* p = trie;
            int ans = 0;
            for(int i = 31; i >= 0; --i) {
                if(p->next[1-((q[0]>>i)&1)]) {
                    p = p->next[1-((q[0]>>i)&1)];
                    ans = (ans<<1) + 1;
                } else {
                    p = p->next[(q[0]>>i)&1];
                    ans <<= 1;
                }
            }

            rets[q[2]] = ans;
        }
        return rets;
    }
};