結果

問題 No.2977 Kth Xor Pair
コンテスト
ユーザー pitP
提出日時 2024-12-02 15:28:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,530 ms / 3,000 ms
コード長 726 bytes
コンパイル時間 397 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 266,316 KB
最終ジャッジ日時 2024-12-02 15:29:28
合計ジャッジ時間 36,118 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import Counter
M = 30


N, K = map(int, input().split())
A = list(map(int, input().split()))
K -= 1

S = [0 for _ in range(M + 2)]
X = [0 for _ in range(M + 2)]
B = [[-1 for _ in range(M + 1)] for _ in range(N)]

for i in range(N):
    for k in range(M + 1):
        B[i][k] = (A[i] >> k) << k

for k in range(M, -1, -1):
    C = Counter()
    for i in range(N):
        C[B[i][k]] += 1
    
    S[k] = S[k + 1]
    X[k] = X[k + 1]

    wa = 0
    for e in C.keys():
        if S[k] == 0:
            wa += C[e] * (C[e] - 1) // 2
        elif ((e ^ S[k]) in C) and (e < (e ^ S[k])):
            wa += C[e] * C[e ^ S[k]]
    
    
    if X[k] + wa <= K:
        S[k] |= 1 << k
        X[k] += wa

print(S[0])
0