#1029432 (PyPy3) No.2977 Kth Xor Pair

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX