結果
問題 |
No.2977 Kth Xor Pair
|
ユーザー |
|
提出日時 | 2024-12-01 00:45:06 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 929 bytes |
コンパイル時間 | 364 ms |
コンパイル使用メモリ | 82,204 KB |
実行使用メモリ | 679,468 KB |
最終ジャッジ日時 | 2024-12-01 00:47:07 |
合計ジャッジ時間 | 120,464 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 3 TLE * 13 MLE * 18 |
ソースコード
import sys, time, random from collections import deque, Counter, defaultdict def debug(*x):print('debug:',*x, file=sys.stderr) input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) inf = 2 ** 61 - 1 mod = 998244353 def xor_str(x, y): return ''.join(str(int(a) ^ int(b)) for a, b in zip(x, y)) n, k = mi() a = li() prefix_counter = Counter() A = [] for v in a: s = bin(v)[2:] while len(s) < 30: s = '0' + s A.append(s) for i in range(30): prefix_counter[s[:i+1]] += 1 ans = '' for i in range(30): #まず0を付けると仮定 zans = ans + '0' zcnt = 0 for v in A: prefix_counter[v[:len(zans)]] -= 1 tocnt = xor_str(zans, v[:len(zans)]) zcnt += prefix_counter[tocnt] if zcnt >= k: ans += '0' else: ans += '1' k -= zcnt print(int(ans, 2))