Editorial for DMOPC '15 Contest 1 P1 - Itami and Manga

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: cheesecake

Sort the ratings in any order and the answer is the name that corresponds with the highest rating.

Time Complexity: \mathcal{O}(N \log N)

Comments


  • 5
    Riolku  commented on Dec. 29, 2018, 8:35 p.m. ← edit 2

    Alternatively, keep a running best rating and name, and then update the best rating. Output the best name at the end.

    This is faster than \mathcal{O}(N \log N), it is \mathcal{O}(N).