提出 #71337977

ソースコード 拡げる

def main():
    N = int(input())
    rabbits = [list(map(int, input().split())) for _ in range(N)]

    dists = set()
    for x, r in rabbits:
        dists.add(x + r)
        dists.add(x - r)
    
    dists = list(dists)
    d_to_idx = {d: i for (i, d) in enumerate(dists)}

    edges = [set() for _ in range(N)]
    for i, (x, r) in enumerate(rabbits):
        left_idx = d_to_idx[x - r]
        right_idx = d_to_idx[x + r]
        edges[i].add(left_idx)
        edges[i].add(right_idx)

    matched = [-1] * len(dists)
    
    visited = [False] * (N + len(dists) + 2)

    def dfs(v):
        for u in edges[v]:
            if visited[u]:
                continue
            visited[u] = True
            if matched[u] == -1 or dfs(matched[u]):
                matched[u] = v
                return True
        return False
    
    result = sum(dfs(s) for s in range(N))
    print(result)

main()

提出情報

提出日時
問題 E - Distribute Bunnies
ユーザ scrblbug
言語 Python (PyPy 3.11-v7.3.20)
得点 0
コード長 941 Byte
結果 WA
実行時間 505 ms
メモリ 306976 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 500
結果
AC × 3
AC × 13
WA × 29
セット名 テストケース
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_00.txt, 01_random_01.txt, 01_random_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, 02_small_cc_00.txt, 02_small_cc_01.txt, 02_small_cc_02.txt, 02_small_cc_03.txt, 02_small_cc_04.txt, 02_small_cc_05.txt, 02_small_cc_06.txt, 02_small_cc_07.txt, 02_small_cc_08.txt, 02_small_cc_09.txt, 02_small_cc_10.txt, 02_small_cc_11.txt, 02_small_cc_12.txt, 02_small_cc_13.txt, 02_small_cc_14.txt, 02_small_cc_15.txt, 02_small_cc_16.txt, 02_small_cc_17.txt, 02_small_cc_18.txt, 02_small_cc_19.txt, 03_path_00.txt, 03_path_01.txt, 04_cycle_00.txt, 04_cycle_01.txt, 05_namori_00.txt, 05_namori_01.txt, 05_namori_02.txt, 05_namori_03.txt, 05_namori_04.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 56 ms 79852 KiB
00_sample_01.txt AC 56 ms 79960 KiB
00_sample_02.txt AC 55 ms 79964 KiB
01_random_00.txt AC 366 ms 223616 KiB
01_random_01.txt WA 455 ms 244016 KiB
01_random_02.txt WA 416 ms 254348 KiB
01_random_03.txt AC 487 ms 306976 KiB
01_random_04.txt AC 368 ms 233424 KiB
01_random_05.txt WA 505 ms 304900 KiB
01_random_06.txt AC 289 ms 172284 KiB
01_random_07.txt WA 477 ms 294868 KiB
01_random_08.txt AC 300 ms 199404 KiB
01_random_09.txt WA 432 ms 220448 KiB
02_small_cc_00.txt AC 483 ms 306412 KiB
02_small_cc_01.txt AC 484 ms 306004 KiB
02_small_cc_02.txt WA 480 ms 293136 KiB
02_small_cc_03.txt WA 472 ms 292680 KiB
02_small_cc_04.txt WA 462 ms 284184 KiB
02_small_cc_05.txt WA 459 ms 283808 KiB
02_small_cc_06.txt WA 455 ms 272320 KiB
02_small_cc_07.txt WA 470 ms 271900 KiB
02_small_cc_08.txt WA 461 ms 271772 KiB
02_small_cc_09.txt WA 462 ms 271560 KiB
02_small_cc_10.txt WA 462 ms 261520 KiB
02_small_cc_11.txt WA 458 ms 261452 KiB
02_small_cc_12.txt WA 448 ms 261044 KiB
02_small_cc_13.txt WA 449 ms 260948 KiB
02_small_cc_14.txt WA 451 ms 251788 KiB
02_small_cc_15.txt WA 448 ms 251508 KiB
02_small_cc_16.txt WA 446 ms 251304 KiB
02_small_cc_17.txt WA 440 ms 251168 KiB
02_small_cc_18.txt WA 439 ms 251028 KiB
02_small_cc_19.txt WA 445 ms 243060 KiB
03_path_00.txt AC 442 ms 232272 KiB
03_path_01.txt AC 452 ms 225440 KiB
04_cycle_00.txt AC 432 ms 232276 KiB
04_cycle_01.txt WA 460 ms 225288 KiB
05_namori_00.txt WA 496 ms 225244 KiB
05_namori_01.txt WA 482 ms 225152 KiB
05_namori_02.txt WA 486 ms 225320 KiB
05_namori_03.txt WA 501 ms 227856 KiB
05_namori_04.txt WA 490 ms 225528 KiB