Loading...
Loading...
Loading...
A live classroom quiz has negative marking, so a score can be below zero. Students submit one by one, and after each submission the screen shows the middle score so far.
Sort the scores received so far from low to high. If there is an odd number of them, the middle one is shown. If there is an even number, the lower of the two middle scores is shown.
Print the shown score after each of the n submissions.
Example 1
Input
5 5 15 1 3 8
Output
5 5 5 3 5
After 4 scores, sorted 1 3 5 15, the two middle scores are 3 and 5, so 3 is shown.
Example 2
Input
4 10 20 30 40
Output
10 10 20 20
Even counts show the lower middle: 10 after two scores and 20 after four.
Try the problem first. Open one hint at a time.
Sorting again after every score is too slow for 10^5 scores. Keep the scores split into a lower half and an upper half.
Keep the lower half in a max-heap and the upper half in a min-heap. Every score in the lower half must be at most every score in the upper half.
After each new score, move one score between the heaps so that the lower half has the same size as the upper half, or one more.
Then the lower middle score is always the top of the lower half.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor