結果
問題 | No.2248 max(C)-min(C) |
ユーザー |
![]() |
提出日時 | 2023-03-20 10:03:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,092 ms / 3,000 ms |
コード長 | 1,631 bytes |
コンパイル時間 | 209 ms |
コンパイル使用メモリ | 82,608 KB |
実行使用メモリ | 226,916 KB |
最終ジャッジ日時 | 2024-09-18 14:00:46 |
合計ジャッジ時間 | 22,194 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
import sysinput = sys.stdin.buffer.readlinefrom heapq import heappop, heappushn = int(input())A = list(map(int, input().split()))B = list(map(int, input().split()))bigpq = []smallpq = []# initialize# a,b,half(a,b)の順に3*i, 3*i+1, 3*i+2のidxをふることにするfor i in range(n):a, b = A[i], B[i]if a > b:heappush(bigpq, (-b, 3 * i + 1))heappush(smallpq, (b, 3 * i + 1))else:heappush(bigpq, (-a, 3 * i))heappush(smallpq, (a, 3 * i))cnt = [0] * nans = 1 << 100finished = set()while True:# print(ans)# print(smallpq)# print(bigpq)now_minimum, smallidx = heappop(smallpq)# smallidxのものはbiggestとして使えないfinished.add(smallidx)# 使用済みbigpqだとアウトwhile bigpq:if bigpq[0][1] in finished:heappop(bigpq)else:break# 使える最大候補がないif not bigpq:breakbiggest, bigidx = bigpq[0]biggest *= -1ans = min(ans, biggest - now_minimum)biggest *= -1# smallidxと同じiのもので、次のものを追加する。idx = smallidx // 3cnt[idx] += 1a, b = A[idx], B[idx]if cnt[idx] == 1:v = (a + b) // 2heappush(bigpq, (-v, 3 * idx + 2))heappush(smallpq, (v, 3 * idx + 2))elif cnt[idx] == 2:if a > b:heappush(bigpq, (-a, 3 * idx))heappush(smallpq, (a, 3 * idx))else:heappush(bigpq, (-b, 3 * idx + 1))heappush(smallpq, (b, 3 * idx + 1))else:breakprint(ans)