結果
問題 | No.2977 Kth Xor Pair |
ユーザー |
|
提出日時 | 2024-12-01 13:10:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,786 ms / 3,000 ms |
コード長 | 708 bytes |
コンパイル時間 | 193 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 124,032 KB |
最終ジャッジ日時 | 2024-12-01 13:11:47 |
合計ジャッジ時間 | 72,316 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
import collections,sys,math,functools,operator,itertools,bisect,heapq,decimal,string,time,random n,k = map(int,input().split()) a = list(map(int,input().split())) a.sort() ans = 0 k-=1 cnt = n*(n-1)//2 - k def calc(x,i): z = 0 for j in a: l = (((j ^ x)>>i) & ((1 << 30)-1)) << i r = l + (1 << i) p = bisect.bisect_left(a,l) q = bisect.bisect_left(a,r) z += q-p #print(x,i,j,l,r,p,q) if l <= j < r: z -= 1 z//=2 #print(x,i,z) return z res = 0 for i in reversed(range(30)): r = calc(ans+(1<<i),i) if res + r >= cnt: ans += 1<<i cnt -= res res = 0 else: res += r print(ans)