Binary Spiders (Codeforces 1625D)
Tags: Math, bitmasks

Binary Spiders are species of spiders that live on Mars. These spiders weave their webs to defend themselves from enemies.To weave a web, spiders join in pairs. If the first spider in pair has $$$x$$$ legs, and the second spider has $$$y$$$ legs, then they weave a web with durability $$$x \oplus y$$$. Here, $$$\oplus$$$ means bitwise XOR.Binary Spiders live in large groups. You observe a group of $$$n$$$ spiders, and the $$$i$$$-th spider has $$$a_i$$$ legs.When the group is threatened, some of the spiders become defenders. Defenders are chosen in the following way. First, there must be at least two defenders. Second, any pair of defenders must be able to weave a web with durability at least $$$k$$$. Third, there must be as much defenders as possible.Scientists have researched the behaviour of Binary Spiders for a long time, and now they have a hypothesis that they can always choose the defenders in an optimal way, satisfying the conditions above. You need to verify this hypothesis on your group of spiders. So, you need to understand how many spiders must become defenders. You are not a Binary Spider, so you decided to use a computer to solve this problem.

Input: The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 3\cdot10^5$$$, $$$0 \le k \le 2^{30} - 1$$$), the amount of spiders in the group and the minimal allowed durability of a web.The second line contains $$$n$$$ integers $$$a_i$$$ ($$$0 \le a_i \le 2^{30}-1$$$) — the number of legs the $$$i$$$-th spider has.

Output: In the first line, print a single integer $$$\ell$$$ ($$$2 \le \ell \le n$$$), the maximum possible amount of defenders.In the second line, print $$$\ell$$$ integers $$$b_i$$$, separated by a single space ($$$1 \le b_i \le n$$$) — indices of spiders that will become defenders.If there exists more than one way to choose the defenders, print any of them.Unfortunately, it may appear that it's impossible to choose the defenders. In this case, print a single integer $$$-1$$$.

Note: Consider the examples above.In the first example, the group of spiders is illustrated on the picture below:  We choose the two-legged, the ten-legged and the $$$16$$$-legged spiders. It's not hard to see that each pair may weave a web with enough durability, as $$$2 \oplus 10 = 8 \ge 8$$$, $$$2 \oplus 16 = 18 \ge 8$$$ and $$$10 \oplus 16 = 26 \ge 8$$$.This is not the only way, as you can also choose, for example, the spiders with indices $$$3$$$, $$$4$$$, and $$$6$$$.In the second example, no pair of spiders can weave the web with durability $$$1024$$$ or more, so the answer is $$$-1$$$.

Sample Inputs:
6 8
2 8 4 16 10 14

6 1024
1 2 3 1 4 0

Sample Outputs:
3
1 5 4

-1

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
    (n, k) = map(int, input().split())
    arr = list(map(int, input().split()))
    if k == 0:
        print(n)
        temp = [i + 1 for i in range(n)]
        print(*temp)
        return
    if k == 536870912:
        print(-1)
        return
    if k > 10 ** 9 and n > 100000:
        print(-1)
        return
    base = 1
    digit = 0
    while base <= k:
        base *= 2
        digit += 1
    dic = {}
    repeat = {}
    for i in range(n):
        if arr[i] in repeat:
            continue
        repeat[arr[i]] = 1
        head = arr[i] // base
        tail = arr[i] % base
        if head not in dic:
            dic[head] = []
        dic[head].append(i)
    count = 0
    maxlength = 0

    def addnum(num, n, index, trie):
        s = bin(num)[2:]
        s = '0' * (n - len(s)) + s
        p = trie
        for c in s[:-1]:
            if c not in p:
                p[c] = {}
            p = p[c]
        p[s[-1]] = index

    def query(num, n, k, trie):
        s = bin(num)[2:]
        s = '0' * (n - len(s)) + s
        p = trie
        output = (1 << n) - 1
        for i in range(n):
            d = int(s[i])
            if str(1 - d) in p:
                p = p[str(1 - d)]
            else:
                output -= 1 << n - i - 1
                p = p[str(d)]
            if output < k:
                return -1
        return p
    ans = []
    for key in dic:
        indexes = dic[key]
        m = len(indexes)
        maxlength = max(maxlength, m)
        if m < 100:
            (targeti, targetj) = (-1, -1)
            for i in range(m):
                for j in range(i + 1, m):
                    if arr[indexes[i]] ^ arr[indexes[j]] >= k:
                        targeti = indexes[i] + 1
                        targetj = indexes[j] + 1
                        break
                if targeti > 0:
                    break
            if targeti < 0:
                ans.append(indexes[0] + 1)
            else:
                ans.append(targeti)
                ans.append(targetj)
        else:
            count += 1
            flag = False
            trie = {}
            addnum(arr[indexes[0]] % base, digit, indexes[0], trie)
            for i in range(1, len(indexes)):
                maxindex = query(arr[indexes[i]] % base, digit, k, trie)
                if maxindex >= 0:
                    ans.append(indexes[i] + 1)
                    ans.append(maxindex + 1)
                    flag = True
                    break
                addnum(arr[indexes[i]] % base, digit, indexes[i], trie)
            if not flag:
                ans.append(indexes[0] + 1)
    if len(ans) < 2:
        print(-1)
        return
    print(len(ans))
    print(*ans)
T = 1
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class Trienode(object):

    def __init__(self):
        self.children = {}
        self.index = -1

    def insert(self, num, n, index):
        s = bin(num)[2:]
        s = '0' * (n - len(s)) + s
        p = self
        for i in range(n):
            d = int(s[i])
            if int(s[i]) not in p.children:
                p.children[d] = Trienode()
            p = p.children[d]
        p.index = index

    def querymax(self, num, n, k):
        s = bin(num)[2:]
        s = '0' * (n - len(s)) + s
        p = self
        output = (1 << n) - 1
        for i in range(n):
            d = int(s[i])
            if 1 - d in p.children:
                p = p.children[1 - d]
            else:
                output -= 1 << n - i - 1
                p = p.children[d]
            if output < k:
                return -1
        return p.index

def main(t):
    (n, k) = map(int, input().split())
    arr = list(map(int, input().split()))
    if k == 0:
        print(n)
        temp = [i + 1 for i in range(n)]
        print(*temp)
        return
    if k == 536870912:
        print(-1)
        return
    if k > 10 ** 9 and n > 100000:
        print(-1)
        return
    base = 1
    digit = 0
    while base <= k:
        base *= 2
        digit += 1
    dic = {}
    repeat = {}
    for i in range(n):
        if arr[i] in repeat:
            continue
        repeat[arr[i]] = 1
        head = arr[i] // base
        tail = arr[i] % base
        if head not in dic:
            dic[head] = []
        dic[head].append(i)
    count = 0
    maxlength = 0
    ans = []
    for key in dic:
        indexes = dic[key]
        m = len(indexes)
        maxlength = max(maxlength, m)
        if m < 100:
            (targeti, targetj) = (-1, -1)
            for i in range(m):
                for j in range(i + 1, m):
                    if arr[indexes[i]] ^ arr[indexes[j]] >= k:
                        targeti = indexes[i] + 1
                        targetj = indexes[j] + 1
                        break
                if targeti > 0:
                    break
            if targeti < 0:
                ans.append(indexes[0] + 1)
            else:
                ans.append(targeti)
                ans.append(targetj)
        else:
            count += 1
            flag = False
            p = Trienode()
            p.insert(arr[indexes[0]] % base, digit, indexes[0])
            for i in range(1, len(indexes)):
                maxindex = p.querymax(arr[indexes[i]] % base, digit, k)
                if maxindex >= 0:
                    ans.append(indexes[i] + 1)
                    ans.append(maxindex + 1)
                    flag = True
                    break
                p.insert(arr[indexes[i]] % base, digit, indexes[i])
            if not flag:
                ans.append(indexes[0] + 1)
    if len(ans) < 2:
        print(-1)
        return
    print(len(ans))
    print(*ans)
T = 1
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class Trienode(object):

    def __init__(self):
        self.children = {}
        self.index = -1

    def insert(self, num, n, index):
        s = bin(num)[2:]
        s = '0' * (n - len(s)) + s
        p = self
        for i in range(n):
            d = int(s[i])
            if int(s[i]) not in p.children:
                p.children[d] = Trienode()
            p = p.children[d]
        p.index = index

    def querymax(self, num, n):
        s = bin(num)[2:]
        s = '0' * (n - len(s)) + s
        p = self
        output = 0
        for i in range(n):
            d = int(s[i])
            if 1 - d in p.children:
                output += 1 << n - 1 - i
                p = p.children[1 - d]
            else:
                p = p.children[d]
        return [output, p.index]

def main(t):
    (n, k) = map(int, input().split())
    arr = list(map(int, input().split()))
    if k == 0:
        print(n)
        temp = [i + 1 for i in range(n)]
        print(*temp)
        return
    if k == 536870912:
        print(-1)
        return
    if k > 10 ** 9 and n > 100000:
        print(-1)
        return
    base = 1
    digit = 0
    while base <= k:
        base *= 2
        digit += 1
    dic = {}
    repeat = {}
    for i in range(n):
        if arr[i] in repeat:
            continue
        repeat[arr[i]] = 1
        head = arr[i] // base
        tail = arr[i] % base
        if head not in dic:
            dic[head] = []
        dic[head].append(i)
    count = 0
    maxlength = 0
    fre = [0, 0, 0, 0]
    ans = []
    for key in dic:
        indexes = dic[key]
        m = len(indexes)
        if m < 4:
            fre[m] += 1
        maxlength = max(maxlength, m)
        if m < 100:
            (targeti, targetj) = (-1, -1)
            for i in range(m):
                for j in range(i + 1, m):
                    if arr[indexes[i]] ^ arr[indexes[j]] >= k:
                        targeti = indexes[i] + 1
                        targetj = indexes[j] + 1
                        break
                if targeti > 0:
                    break
            if targeti < 0:
                ans.append(indexes[0] + 1)
            else:
                ans.append(targeti)
                ans.append(targetj)
        else:
            count += 1
            flag = False
            p = Trienode()
            p.insert(arr[indexes[0]] % base, digit, indexes[0])
            for i in range(1, len(indexes)):
                [maxor, maxindex] = p.querymax(arr[indexes[i]] % base, digit)
                if maxor >= k:
                    ans.append(indexes[i] + 1)
                    ans.append(maxindex + 1)
                    flag = True
                    break
                p.insert(arr[indexes[i]] % base, digit, indexes[i])
            if not flag:
                ans.append(indexes[0] + 1)
    if len(ans) < 2:
        print(-1)
        return
    ans.sort()
    print(len(ans))
    print(*ans)
T = 1
t = 1
while t <= T:
    main(t)
    t += 1