Wesley's Anger Contest 3 Problem 6 - Zeyu's Sadness Contest 1

View as PDF

Submit solution


Points: 30 (partial)
Time limit: 5.0s
Memory limit: 512M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Zeyu is making his first ever Sadness Contest! His contest consists of M problems (numbered from 1 to M) with N contestants participating (numbered from 1 to N).

The rules of his contests are as follows:

  • The contest lasts for 10\,000\,000 minutes.
  • Each contestant may submit at most 10\,000\,000 times to each problem.
  • Contestants are ordered by the number of problems solved. The more problems they solved, the better their rank.
  • If there is a tie in the number of problems solved, then contestants are ordered by the sum of the times used to solve the problems (in minutes) starting from the beginning of the contest, plus 10 minutes for each incorrect submission to a problem they solved. Note that there is no penalty for incorrect submissions to problem that they did not solve. The smaller their sum of times plus penalty, the better their rank.
  • If there is also a tie in the sum of times plus penalty, then the contestants are ordered by their identification number. The smaller their indentification number, the better their rank.

You have been given a list of all K accepted submissions in the contest. You know the order that they were submitted, which contestant it was submitted by (c_i), which problem it was submitted to (p_i), and the rank of the contestant after their submission (r_i). Unfortuntately, you have lost all incorrect submissions in the contest, as well as the specific times of the accepted submissions. Given this partial list of submission, can you recreate any scoreboard that is consistent with this list?

It is guaranteed that no contestant submitted an incorrect submission to a problem they already solved and that no two contestants had an accepted submission in the same minute. It is also guaranteed that a valid scoreboard can be recreated from the partial submission list.

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

1 \le N \le 200\,000
1 \le M \le 3
0 \le K \le N \cdot M
1 \le c_i \le N
1 \le p_i \le M
1 \le r_i \le N

Subtask 1 [10%]

1 \le N \le 2\,000
M = 1

Subtask 2 [20%]

1 \le N \le 2\,000

Subtask 3 [20%]

M = 1

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains 3 integers, N, M, and K, indicating that Zeyu's contest has N contestants, M problems, and K accepted submissions.

The next K lines describe the accepted submissions in the order that they were submitted. Each line contains 3 integers, c_i, p_i, and r_i, indicating that this submission was made by the c_i^{th} contestant to the p_i^{th} problem, and that they were rank r_i after this submission. It is guaranteed that this list of accepted submissions was created from a valid scoreboard.

Output Specification

Output N lines, describing any scoreboard that is consistent with the given list of accepted submissions. It is guaranteed that such a scoreboard exists. The scoreboard is listed in ascending order of the contestants' final rank.

The i^{th} line should consist of M + 1 strings in the following format:

  • The first string should be an integer a_i in the range [1, N] representing the identification number of the contest who was rank i at the end of the contest.
  • The next M strings describe the submissions the a_i^{th} contestant made. The j^{th} of these strings should be in the form <time>/<penalty>. <time> is an integer in the range [1, 10\,000\,000] representing the time in minutes that the a_i^{th} contestant submitted to the j^{th} problem. <penalty> is an integer in the range [0, 9\,999\,999] representing the number of incorrect submissions that the a_i^{th} contestant made to the j^{th} problem. If the a_i^{th} contestant did not solve the j^{th} problem, then the j^{th} string should be -/- instead of the format described. Note that all accepted submission times must be unique.

Note that for this problem, a verdict involving Presentation Error indicates that your output format is incorrect or the output does not represent a valid scoreboard, (including, but not limited to not outputting the contestants in the order of their final rank).

Sample Input 1

3 1 2
3 1 1
1 1 1

Sample Output 1

1 10/0
3 1/5
2 -/-

Sample Explanation 1

After the first accepted submission at 1 minute, with 5 incorrect submissions by contestant 3, they move to first place. After the second accepted submission at 10 minutes, with 0 incorrect submissions by contestant 1, they move to first place.

Sample Input 2

2 3 6
2 2 1
1 3 1
1 2 1
2 1 2
1 1 1
2 3 1

Sample Output 2

2 45/3 8/1 67/3
1 59/6 22/5 18/0

Sample Explanation 2

Note that after the first two submissions, there is a tie in the sum of submission times plus penalties. Since contestant 1 has a smaller identification number, they are considered to be first place.


Comments

There are no comments at the moment.