List Minimum (Hard)

View as PDF
Submit solution
Points: 5
Time limit: 0.4s
Racket 1.0s
Memory limit: 256M
Problem type
Brute Force Practice 1 — Hard Version

You have a list of unique numbers each no larger than 10^9. The size of the list is no greater than 10^5. You perform the following operation on the list repeatedly: take the minimum of the numbers, and remove it from the list. You stop when the list is empty.

In what order are the numbers removed?

Input Specification

The first line will have the size of the list.

Each line after that will be an element of the list. You are guaranteed no two elements are the same.

Output Specification

Print one line for each time the operation was performed: the number that was removed at that step.

Sample Input

3
5
8
2

Sample Output

2
5
8

Comments


  • 0
    daveys  commented on Feb. 29, 2024, 9:54 a.m.

    This forced me to re-think my code from List Minimum (Easy), which is useful. There's a really simple way to solve this and I missed that on the easy version.


  • 4
    dxke02  commented on Nov. 19, 2020, 5:05 p.m.

    I submitted a solution in java a TLE'd then did the same code in c++ and AC'd.


  • 2
    LucaC  commented on Sept. 14, 2020, 9:48 a.m.

    Wait, is this not the same problem as List Minimum (https://dmoj.ca/problem/bf1)? The instructions are worded differently, but the problem seems the same. I even used the same code for both. Could someone explain this?


    • 0
      Viv_CCGS  commented on Nov. 2, 2021, 12:14 p.m.

      Yeah, he’s right.

      My code for List Minimum is the same as the List Minimum (Hard)

      This is rather random, given that the AC is smaller by at least 20%


    • 5
      AlanL  commented on Sept. 14, 2020, 1:58 p.m. ← edited

      The constraints of the problems are different. The ones in this problem are a lot larger than the other one, so some solutions (not yours apparently) that may AC the other one may fail this one.


      • -4
        bestcreatorT  commented on Sept. 25, 2020, 7:32 a.m.

        like mine


      • 3
        LucaC  commented on Sept. 15, 2020, 4:55 a.m.

        Ah, that clears things up, Thank you!


  • 0
    FatalEagle  commented on Oct. 23, 2016, 12:26 a.m. ← edited

    To deal with input/output, you may want to add this to your program:

    (void (map displayln (my-sort (build-list (read) (lambda (x) (read))) <)))


  • 5
    FatalEagle  commented on Nov. 14, 2014, 3:57 p.m. ← edited

    For Java users getting TLE on the last case, reading this might be helpful.


    • 0
      IanHu  commented on Oct. 9, 2018, 11:54 p.m.

      Thx a lot