結果
問題 | No.2977 Kth Xor Pair |
ユーザー |
![]() |
提出日時 | 2024-12-08 16:39:52 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,449 bytes |
コンパイル時間 | 317 ms |
コンパイル使用メモリ | 82,096 KB |
実行使用メモリ | 166,148 KB |
最終ジャッジ日時 | 2024-12-08 16:40:18 |
合計ジャッジ時間 | 24,690 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 RE * 29 |
ソースコード
def walsh_hadamard_transform(f):k = (len(f) - 1).bit_length()h = 1for _ in range(k):for i in range(0, len(f), h * 2):for j in range(i, i + h):f[j], f[j + h] = f[j] + f[j + h], f[j] - f[j + h]h *= 2def Xor_convolution(a, b):f = a[:]g = b[:]k = (len(f) - 1).bit_length()walsh_hadamard_transform(f)walsh_hadamard_transform(g)for i in range(1 << k):f[i] = f[i] * g[i]walsh_hadamard_transform(f)for i in range(len(f)):f[i] >>= kreturn fN, K = map(int, input().split())A = list(map(int, input().split()))F = [0 for i in range(1 << 20)]for a in A:F[a >> 10] += 1F = Xor_convolution(F, F)F[0] -= Nfor i in range(1 << 20):F[i] //= 2if i > 0:F[i] += F[i - 1]i = 0while F[i] < K:i += 1mask = ians = i << 10G = [[] for i in range(1 << 20)]for a in A:b = a >> 10G[b].append(a - (b << 10))F = [0 for i in range(1 << 10)]for i in range(1 << 20):c = min(len(G[i]), len(G[mask ^ i]))if c <= 100:for j in G[i]:for k in G[i ^ mask]:F[j ^ k] += 1else:f, g = [0 for _ in range(1 << 10)], [0 for _ in range(1 << 10)]for j in G[i]:f[j] += 1for k in G[i ^ mask]:g[k] += 1f = Xor_convolution(f, g)for j in range(1 << 10):F[j] += f[j]if mask == 0:F[0] -= Nfor i in range(1 << 10):F[i] //= 2if i > 0:F[i] += F[i - 1]i = 0while F[i] < K:i += 1ans += iprint(ans)