結果
| 問題 |
No.2977 Kth Xor Pair
|
| コンテスト | |
| ユーザー |
 LyricalMaestro
|
| 提出日時 | 2025-10-30 01:22:01 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,085 ms / 3,000 ms |
| コード長 | 5,938 bytes |
| コンパイル時間 | 382 ms |
| コンパイル使用メモリ | 82,360 KB |
| 実行使用メモリ | 156,552 KB |
| 最終ジャッジ日時 | 2025-10-30 01:22:32 |
| 合計ジャッジ時間 | 30,817 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 34 |
ソースコード
## https://yukicoder.me/problems/no/2977
def solve2(N, K, A):
array = []
for i in range(N):
for j in range(i + 1, N):
array.append(A[i] ^ A[j])
array.sort()
print(array[K - 1])
def main():
N, K = map(int, input().split())
A = list(map(int, input().split()))
max_a = max(A)
for k in reversed(range(40)):
if (1 << k) & max_a > 0:
max_k = k
break
A.sort()
answer = 0
target_ranges = [[i + 1, N - 1] for i in range(N)]
target_ranges[N - 1] = [-1, -1]
for k in reversed(range(max_k + 1)):
array = [-1] * N
for i in range(N):
array[i] = 1 if (1 << k) & A[i] > 0 else 0
# 0の数を計算
z = 0
for i in range(N):
if target_ranges[i][0] == -1:
continue
if array[i] == 0:
if array[target_ranges[i][1]] == 0:
z += target_ranges[i][1] - target_ranges[i][0] + 1
elif array[target_ranges[i][0]] == 0:
low = target_ranges[i][0]
high = target_ranges[i][1]
while high - low > 1:
mid = (high + low) // 2
if array[mid] == 0:
low = mid
else:
high = mid
if array[high] == 0:
z += high - target_ranges[i][0] + 1
else:
z += low - target_ranges[i][0] + 1
else:
if array[target_ranges[i][0]] == 1:
z += target_ranges[i][1] - target_ranges[i][0] + 1
elif array[target_ranges[i][1]] == 1:
low = target_ranges[i][0]
high = target_ranges[i][1]
while high - low > 1:
mid = (high + low) // 2
if array[mid] == 1:
high = mid
else:
low = mid
if array[low] == 1:
z += target_ranges[i][1] - low + 1
else:
z += target_ranges[i][1] - high + 1
if z < K:
K -= z
answer += (1 << k)
for i in range(N):
if target_ranges[i][0] == -1:
continue
if array[i] == 0:
if array[target_ranges[i][1]] == 0:
target_ranges[i][0] = -1
target_ranges[i][1] = -1
continue
else:
# 1を求める
low = target_ranges[i][0]
high = target_ranges[i][1]
while high - low > 1:
mid = (high + low) // 2
if array[mid] == 1:
high = mid
else:
low = mid
if array[low] == 1:
target_ranges[i][0] = low
else:
target_ranges[i][0] = high
else:
if array[target_ranges[i][0]] == 1:
target_ranges[i][0] = -1
target_ranges[i][1] = -1
continue
else:
# 0を求める
low = target_ranges[i][0]
high = target_ranges[i][1]
while high - low > 1:
mid = (high + low) // 2
if array[mid] == 0:
low = mid
else:
high = mid
if array[high] == 0:
target_ranges[i][1] = high
else:
target_ranges[i][1] = low
else:
# 0となる範囲を求める
for i in range(N):
if target_ranges[i][0] == -1:
continue
if array[i] == 0:
if array[target_ranges[i][0]] == 1:
target_ranges[i][0] = -1
target_ranges[i][1] = -1
continue
else:
low = target_ranges[i][0]
high = target_ranges[i][1]
while high - low > 1:
mid = (high + low) // 2
if array[mid] == 0:
low = mid
else:
high = mid
if array[high] == 0:
target_ranges[i][1] = high
else:
target_ranges[i][1] = low
else:
if array[target_ranges[i][1]] == 0:
target_ranges[i][0] = -1
target_ranges[i][1] = -1
continue
else:
low = target_ranges[i][0]
high = target_ranges[i][1]
while high - low > 1:
mid = (high + low) // 2
if array[mid] == 1:
high = mid
else:
low = mid
if array[low] == 1:
target_ranges[i][0] = low
else:
target_ranges[i][0] = high
print(answer)
if __name__ == "__main__":
main()