結果

問題 No.1240 Or Sum of Xor Pair
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:11:20
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,722 bytes
コンパイル時間 473 ms
コンパイル使用メモリ 82,596 KB
実行使用メモリ 284,576 KB
最終ジャッジ日時 2025-06-12 13:14:20
合計ジャッジ時間 11,060 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

def insert(node, number):
    for bit in reversed(range(18)):
        b = (number >> bit) & 1
        if not node.children[b]:
            node.children[b] = TrieNode()
        node = node.children[b]
        node.count += 1

def query(node, a, X):
    count = 0
    current = node
    for bit in reversed(range(18)):
        if not current:
            break
        a_bit = (a >> bit) & 1
        x_bit = (X >> bit) & 1
        if x_bit == 1:
            if current.children[a_bit]:
                count += current.children[a_bit].count
            desired_bit = 1 - a_bit
            current = current.children[desired_bit] if current.children[desired_bit] else None
        else:
            desired_bit = a_bit
            current = current.children[desired_bit] if current.children[desired_bit] else None
    return count

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    X = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N

    # Compute T
    root_T = TrieNode()
    count_T = 0
    for a in A:
        count_T += query(root_T, a, X)
        insert(root_T, a)
    
    total = 0
    # For each bit b, compute C_b
    for b in range(18):
        S_b = [a for a in A if (a & (1 << b)) == 0]
        root_C = TrieNode()
        count_C = 0
        for a in S_b:
            count_C += query(root_C, a, X)
            insert(root_C, a)
        contribution = (count_T - count_C) * (1 << b)
        total += contribution
    print(total)

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