提出 #76821739

ソースコード 拡げる

from operator import itemgetter

N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(N)]
LR.sort(key=itemgetter(1))
ok = 0
ng = 10**10
while ok + 1 < ng:
    mid = (ok + ng) // 2
    j = 0
    i = 1
    t = 1
    while i < N:
        if LR[i][0] >= LR[j][1] + mid:
            j = i
            t += 1
        i += 1
    if t >= K:
        ok = mid
    else:
        ng = mid
print(ok if ok > 0 else -1)

提出情報

提出日時
問題 D - Maximize the Gap
ユーザ shogo314
言語 Python (PyPy 3.11-v7.3.20)
得点 400
コード長 461 Byte
結果 AC
実行時間 621 ms
メモリ 127564 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 3
AC × 27
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 60 ms 81964 KiB
00_sample_01.txt AC 60 ms 82324 KiB
00_sample_02.txt AC 60 ms 82368 KiB
01_random_03.txt AC 570 ms 127004 KiB
01_random_04.txt AC 567 ms 127176 KiB
01_random_05.txt AC 564 ms 127008 KiB
01_random_06.txt AC 573 ms 127212 KiB
01_random_07.txt AC 577 ms 126984 KiB
01_random_08.txt AC 589 ms 126960 KiB
01_random_09.txt AC 616 ms 127164 KiB
01_random_10.txt AC 568 ms 126980 KiB
01_random_11.txt AC 570 ms 127468 KiB
01_random_12.txt AC 574 ms 126824 KiB
01_random_13.txt AC 571 ms 126948 KiB
01_random_14.txt AC 605 ms 127180 KiB
01_random_15.txt AC 621 ms 127080 KiB
01_random_16.txt AC 605 ms 127192 KiB
01_random_17.txt AC 608 ms 127336 KiB
01_random_18.txt AC 618 ms 126444 KiB
01_random_19.txt AC 606 ms 127232 KiB
01_random_20.txt AC 604 ms 127564 KiB
01_random_21.txt AC 604 ms 127036 KiB
01_random_22.txt AC 593 ms 126996 KiB
01_random_23.txt AC 615 ms 127192 KiB
01_random_24.txt AC 534 ms 126952 KiB
01_random_25.txt AC 60 ms 82124 KiB
01_random_26.txt AC 60 ms 82248 KiB