結果

問題 No.130 XOR Minimax
コンテスト
ユーザー vjudge1
提出日時 2025-11-13 22:49:18
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 1,584 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 174,540 KB
最終ジャッジ日時 2025-11-13 22:49:56
合計ジャッジ時間 33,153 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

class TrieNode:
    __slots__ = ['children'] 
    def __init__(self):
        self.children = [None, None]

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1  
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]
    
    def query(self, s):
        node = self.root
        max_xor_k = 0
        for i in range(31, -1, -1):
            current_bit = (s >> i) & 1
            target_bit = 1 - current_bit if node.children[1 - current_bit] else current_bit
            max_xor_k |= (target_bit << i) 
            node = node.children[target_bit]
        return max_xor_k
    
    def clear(self, node=None):
        if node is None:
            node = self.root
        for child in node.children:
            if child:
                self.clear(child)
        del node

def main():
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    for case in range(1, T + 1):
        N = int(input[ptr])
        M = int(input[ptr + 1])
        ptr += 2
        nums = list(map(int, input[ptr:ptr + N]))
        ptr += N
        trie = Trie()
        for num in nums:
            trie.insert(num)
        print(f"Case #{case}:")
        for _ in range(M):
            S = int(input[ptr])
            ptr += 1
            print(trie.query(S))
        trie.clear()

if __name__ == "__main__":
    main()
0