結果

問題 No.2977 Kth Xor Pair
コンテスト
ユーザー LyricalMaestro
提出日時 2025-10-30 00:26:11
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,968 bytes
コンパイル時間 308 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 849,008 KB
最終ジャッジ日時 2025-10-30 00:26:20
合計ジャッジ時間 8,715 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other MLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/2977


def solve2(N, K, A):
    array = []
    for i in range(N):
        for j in range(i + 1, N):
            array.append(A[i] ^ A[j])
    array.sort()
    print(array[K - 1])


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    max_a = max(A)
    for k in reversed(range(40)):
        if (1 << k) & max_a > 0:
            max_k = k
            break

    keys_pairs = [(0, 0)]
    keys_map = {0: A}
    answer = 0
    for k in reversed(range(max_k + 1)):
        new_keys_map = {}
        new_k = 0
        new_a_key_map = {}
        for a_key, a_array in keys_map.items():
            a0 = []
            a1 = []
            for a in a_array:
                if (1 << k) & a > 0:
                    a1.append(a)
                else:
                    a0.append(a)
            new_keys_map[new_k] = a0
            new_keys_map[new_k +1] = a1
            new_a_key_map[a_key] = (new_k, new_k + 1)
            new_k += 2
        
        new_key_pairs = {0: [], 1: []}
        for p1, p2 in keys_pairs:
            k0, k1 = new_a_key_map[p1]
            l0, l1 = new_a_key_map[p2]
            new_key_pairs[0].append((k0, l0))
            new_key_pairs[0].append((k1, l1))
            if p1 == p2:
                new_key_pairs[1].append((k0, l1))
            else:
                new_key_pairs[1].append((k0, l1))
                new_key_pairs[1].append((k1, l0))


        x = 0        
        for k0, k1 in new_key_pairs[0]:
            b0 = len(new_keys_map[k0])
            b1 = len(new_keys_map[k1])
            if k0 == k1:
                x += (b0 * (b0 - 1)) // 2
            else:
                x += b0 * b1

        if x < K:
            K -= x
            answer += (1 << k)
            keys_pairs = new_key_pairs[1]
        else:
            keys_pairs = new_key_pairs[0]
        keys_map = new_keys_map


    print(answer)





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