Submission #71861922

Source Code Expand

def main():
    N = int(input())
    dat = [list(map(int, input().split())) for _ in range(N)]
    nodes = [[dict(), []]]
    
    idx_to_nodeidx = [-1] * (N + 1)
    idx_to_nodeidx[0] = 0


    for i, (x, y) in enumerate(dat, start=1):
        x_nodeidx = idx_to_nodeidx[x]
        if y in nodes[x_nodeidx][0]:
            nodeidx = nodes[x_nodeidx][0][y]
            idx_to_nodeidx[i] = nodeidx
            nodes[nodeidx][1].append(i)
        else:
            nodeidx = len(nodes)
            nodes.append([dict(), [i]])
            nodes[x_nodeidx][0][y] = nodeidx
            idx_to_nodeidx[i] = nodeidx
    
    result = []

    queue = [0]
    while queue:
        now = queue.pop()
        for v in nodes[now][1]:
            result.append(v)
        nxts = list(nodes[now][0].keys())
        nxts.sort(reverse=True)
        for nxt in nxts:
            queue.append(nodes[now][0][nxt])

    print(*result)

main()

Submission Info

Submission Time
Task E - Sort Arrays
User scrblbug
Language Python (PyPy 3.11-v7.3.20)
Score 450
Code Size 963 Byte
Status AC
Exec Time 1054 ms
Memory 293704 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 3
AC × 48
Set Name Test Cases
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_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt, 01_test_33.txt, 01_test_34.txt, 01_test_35.txt, 01_test_36.txt, 01_test_37.txt, 01_test_38.txt, 01_test_39.txt, 01_test_40.txt, 01_test_41.txt, 01_test_42.txt, 01_test_43.txt, 01_test_44.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 50 ms 80064 KiB
00_sample_01.txt AC 50 ms 80068 KiB
00_sample_02.txt AC 50 ms 79828 KiB
01_test_00.txt AC 152 ms 118804 KiB
01_test_01.txt AC 564 ms 183012 KiB
01_test_02.txt AC 392 ms 149120 KiB
01_test_03.txt AC 648 ms 179816 KiB
01_test_04.txt AC 507 ms 173680 KiB
01_test_05.txt AC 837 ms 208020 KiB
01_test_06.txt AC 318 ms 151600 KiB
01_test_07.txt AC 946 ms 231788 KiB
01_test_08.txt AC 131 ms 117344 KiB
01_test_09.txt AC 978 ms 249084 KiB
01_test_10.txt AC 973 ms 254040 KiB
01_test_11.txt AC 1031 ms 257640 KiB
01_test_12.txt AC 196 ms 130756 KiB
01_test_13.txt AC 1030 ms 258368 KiB
01_test_14.txt AC 342 ms 158380 KiB
01_test_15.txt AC 1013 ms 256868 KiB
01_test_16.txt AC 514 ms 180372 KiB
01_test_17.txt AC 1035 ms 258404 KiB
01_test_18.txt AC 133 ms 117928 KiB
01_test_19.txt AC 1054 ms 258480 KiB
01_test_20.txt AC 555 ms 194408 KiB
01_test_21.txt AC 552 ms 189180 KiB
01_test_22.txt AC 697 ms 293704 KiB
01_test_23.txt AC 626 ms 234072 KiB
01_test_24.txt AC 537 ms 195368 KiB
01_test_25.txt AC 584 ms 189864 KiB
01_test_26.txt AC 685 ms 293552 KiB
01_test_27.txt AC 613 ms 233304 KiB
01_test_28.txt AC 540 ms 191264 KiB
01_test_29.txt AC 720 ms 245880 KiB
01_test_30.txt AC 690 ms 293500 KiB
01_test_31.txt AC 618 ms 235340 KiB
01_test_32.txt AC 550 ms 185364 KiB
01_test_33.txt AC 722 ms 251848 KiB
01_test_34.txt AC 648 ms 293576 KiB
01_test_35.txt AC 595 ms 234756 KiB
01_test_36.txt AC 503 ms 176520 KiB
01_test_37.txt AC 680 ms 258044 KiB
01_test_38.txt AC 629 ms 293400 KiB
01_test_39.txt AC 576 ms 234544 KiB
01_test_40.txt AC 546 ms 179348 KiB
01_test_41.txt AC 671 ms 258188 KiB
01_test_42.txt AC 652 ms 293284 KiB
01_test_43.txt AC 642 ms 236908 KiB
01_test_44.txt AC 50 ms 80164 KiB