Good Strategy

View as PDF

Submit solution

Points: 10
Time limit: 7.0s
Memory limit: 64M

Author:
Problem type

The ACM-ICPC World Finals have begun! However, let's not be too hasty - even though The Team features three of the best coders to have ever coded, they know the importance of first determining what to code.

The contest features N (1 \le N \le 10^6) problems (conveniently numbered 1 \dots N), and runs for M (1 \le M \le 10^6) minutes. Every problem is associated with a distinct colour - and each time a team solves a problem, they receive a balloon of its corresponding colour, which is visible to all. Obviously, easier problems will be solved by more teams, and so more of their balloons will be floating around in the contest room. Additionally, The Team has found that earlier problems in the set tend to be easier. Therefore, given 2 problems i and j, i is considered easier than j if there are either more i balloons than j balloons in the room, or there are an equal number of balloons and i < j.

At the start of the contest (at the 0th minute), there are no balloons in the room, of course. After that, during every minute i (for i = 1 \dots M), problem p_i (1 \le p_i \le N) is either solved by The Team (which will only happen if they have not solved it previously), or by some opposing team. The former possibility is represented by t_i = 1, and the latter by t_i = 2. In either case, a p_i balloon is brought into the room. However, in the former case, The Team will no longer care about problem p_i in the slightest.

At the end of every minute after the 0th one, the members of The Team want to get their bearings on what they should be working on (and what they should be staying away from). Specifically, out of problems that they haven't yet solved, they want to know what the single easiest and the single hardest problems are, given the information that can be gleaned from the balloons. These two values may be the same, if The Team has only one problem left to solve. If they've solved all of the problems already, they can instead commence the process of making distracting noises. Are you smart enough to figure out what The Team's strategy throughout the contest will be?

Input Specification

First line: 2 integers, N and M
Next M lines: 2 integers, t_i and p_i, for i = 1 \dots M

Output Specification

M lines: Either 2 integers, the easiest followed by the hardest unsolved problem number after the first i minutes, or the string Make noise if all problems have been solved by The Team, for i = 1 \dots M.

Sample Input

3 8
2 2
2 1
1 1
2 3
2 3
1 2
1 3
2 1

Sample Output

2 3
1 3
2 3
2 3
3 2
3 3
Make noise
Make noise

Explanation of Sample

After the first minute, we've seen 1 balloon for problem 2, and 0 balloons for problems 1 and 3. Therefore, the easiest problem is 2, since it has the most balloons, and the hardest problem is 3, since it's the last problem with the least balloons.

After the second minute, the counts for the 3 problems are 1, 1, and 0. The easiest problem is now 1, since it's the first problem with the most balloons, while the hardest is still 3.

After the third minute, the counts for the 3 problems are 2, 1, and 0, but problem 1 has now been solved by The Team. The easiest remaining problem is 2, and the hardest is 3.

After the fourth minute, the counts for the 3 problems are 2 (solved), 1, and 1. The easiest unsolved problem is 2, and the hardest is 3.

After the fifth minute, the counts for the 3 problems are 2 (solved), 1, and 2. The easiest unsolved problem is 3, and the hardest is 2.

After the sixth minute, the counts for the 3 problems are 2 (solved), 2 (solved), and 2. The only unsolved problem is 3.

After the seventh and eighth minutes, all 3 problems have been solved by The Team, so noise should be made.


Comments


  • 6
    julian33  commented on Nov. 11, 2020, 10:37 p.m. edited

    problem 𝑝𝑖 (1≤𝑝𝑖≤𝑁) is either solved by The Team (which will only happen if they have not solved it previously)

    I think it should be noted that the input actually does give a scenario where the team is given a problem to solve which they already solved. Not sure if I just misinterpreted this statement or if there is an inconsistency with the problem statement and the input data.


    • 4
      SourSpinach  commented on Nov. 14, 2020, 5:45 a.m. edited

      Thanks for pointing that out! That issue affects case #4, and we'll get it corrected.