結果

問題 No.2977 Kth Xor Pair
ユーザー 👑 tatyam
提出日時 2024-12-02 00:10:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 270 ms / 3,000 ms
コード長 1,701 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 117,100 KB
最終ジャッジ日時 2024-12-02 00:11:05
合計ジャッジ時間 9,680 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

X = [0] * (1 << 17)
for a in A:
    X[a >> 13] += 1

def FWT(X) -> None:
    N = len(X)
    n = N.bit_length() - 1
    for i in range(n):
        d = 1 << i
        for j in range(N):
            if (j & d) == 0:
                x = X[j]
                y = X[j | d]
                X[j] = x + y
                X[j | d] = x - y

def IFWT(X) -> None:
    N = len(X)
    n = N.bit_length() - 1
    for i in range(n):
        d = 1 << i
        for j in range(N):
            if (j & d) == 0:
                x = X[j]
                y = X[j | d]
                X[j] = (x + y) >> 1
                X[j | d] = (x - y) >> 1

def xor_conv(X, Y) -> list[int]:
    N = len(X)
    X = X[:]
    Y = Y[:]
    FWT(X)
    FWT(Y)
    for i in range(N):
        X[i] *= Y[i]
    IFWT(X)
    return X

X = xor_conv(X, X)

for upper in range(1 << 17):
    if X[upper] <= K:
        K -= X[upper]
    else:
        break

B = [[] for _ in range(1 << 17)]
LO = (1 << 13) - 1
for a in A:
    B[a >> 13].append(a & LO)

S = [0] * (1 << 13)
for i in range(1 << 17):
    j = upper ^ i
    if len(B[i]) == 0 or len(B[j]) == 0:
        continue
    if len(B[i]) * len(B[j]) <= 13 << 13:
        for a in B[i]:
            for b in B[j]:
                S[a ^ b] += 1
    else:
        X = [0] * (1 << 13)
        for a in B[i]:
            X[a] += 1
        Y = [0] * (1 << 13)
        for b in B[j]:
            Y[b] += 1
        Z = xor_conv(X, Y)
        for k in range(1 << 13):
            S[k] += Z[k]

for lower in range(1 << 13):
    if S[lower] <= K:
        K -= S[lower]
    else:
        break

print(upper << 13 | lower)
0