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)$ ~\mathcal{O}(N \log N)~

Comments

5

Riolku commented on Dec. 29, 2018, 8:35 p.m. ← edited →

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 $O(N \log N)$ ~O(N \log N)~, it is $O(N)$ ~O(N)~.