結果

問題 No.130 XOR Minimax
ユーザー lam6er
提出日時 2025-03-20 21:13:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 943 ms / 5,000 ms
コード長 1,019 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,664 KB
実行使用メモリ 289,248 KB
最終ジャッジ日時 2025-03-20 21:14:53
合計ジャッジ時間 11,517 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    def insert(self, num, bit):
        if bit < 0:
            return
        b = (num >> bit) & 1
        if not self.children[b]:
            self.children[b] = TrieNode()
        self.children[b].insert(num, bit - 1)

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    a = list(map(int, input[1:n+1]))

    max_bit = 30
    root = TrieNode()
    for num in a:
        root.insert(num, max_bit)

    def min_max_xor(node, bit):
        if bit < 0:
            return 0
        left = node.children[0]
        right = node.children[1]
        if not left and not right:
            return 0
        if not left or not right:
            child = left if left else right
            return min_max_xor(child, bit - 1)
        else:
            return (1 << bit) + min(min_max_xor(left, bit - 1), min_max_xor(right, bit - 1))

    print(min_max_xor(root, max_bit))

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