ICPC Ranking

Time Limit: 20000/10000 MS (Java/Others)

Memory Limit: 132768/132768 K (Java/Others)

Description

  There are so many submissions during this contest. Coach Pang can not determine which team is the winner. Could you help him to print the score board?
  As we all know, the contest executes by the teams submit codes for some problems. Simply, we assume there are three kinds of results for every submission.

  ERROR There was something wrong. The team didn’t solve the problem but won’t get any penalty.
  NO Sorry, the code was not right. The team didn’t solve the problem.
  YES Yeah, AC. The team solved the problem.

  To make the contest more exciting, we set a time called frozen time. If one team doesn’t solve one of the problems before the frozen time and submits at least one submission on this problem after or exactly at the frozen time, this problem of this team is called frozen. For different team, the frozen problems will be different. For the frozen problems, the score board will only show how many submissions the team has been submitted but won’t show the result of the submissions.
  The rank is determined by the following factors. Remember, we only consider the unfrozen problems. The frozen problems will be ignored. The following factors are ordered with the priority from high to low.

  Solved the team who solves more problems will place higher.
  Penalty the team who gets less penalty time will place higher. Only solved problems will give penalty time. Every solved problem will give T + 20X penalty time. T is the time of the first YES, X is the number of NOs before the first YES.
  Last Solved the team who solved their last problem earlier will place higher. If there is a tie, we compare their second last problems, then their third last problems, etc.
  Name The team whose name comes later in lexicographical order will place higher.

  At the end of the contest, the score board will be unfrozen. First, choose the team which has frozen problems with the lowest rank. Then choose one frozen problem of this team. If the team has multiple frozen problems, choose their first frozen problem in alphabetic order. Then show the result of the problem, recalculate the rank, change the score board and make the problem unfrozen for this team. Repeat this procedure until no teams have frozen problems. Then we get the final score board.

  Please help Coach Pang to print the initial score board, the final score board and the process of the unfreeze procedure.

Input

  The first line contains an integer C, which indicates the number of test cases.
  For each test case, the first line will have four integers n, m, T and t. n(1 <= n <= 50000) is the number of submissions. m(1 <= m <= 26) is the number of problems. T(1 <= T <= 10000) is the total time of the contest. t(0 <= t <= T) is the frozen time.

  The following n lines, each line will be in the form "Name Problem Time Result". Name is the team’s name which only contains letters and digits with at most 20 characters. Problem is the identifier of the problem which is a capital letter from A to them-th letter. Time is a integer indicates the submission time which greater than or equal to 0 and less than T. Result is one string which equal YES, NO or ERROR.
  Every team will have at least one submission. If one team has multiple submissions at the same time, we consider the ERRORs come before NOs and NOs come before YESs.

Output

  For each test case, first print “Case #x:”, x is the case number start from 1.
  Then print the initial score board (before the unfreeze procedure) ordered by the rank. For every team, print "Name Rank Solved Penalty A B C ...". Name is the team’s name. Rank is the team’s rank. Solved is the number of solved problems. Penalty is the team’s penalty time.
A B C ... is the condition of every problem is the format below:

  +x The problem is unfrozen and solved. x is the number of NOs before the first YES. If x = 0, print "+" instead of "+0".

  -x The problem is unfrozen but not solved. x is the number of NOs. If x = 0, print "." instead of "-0".

  -x/y The problem is frozen. x is the number of NOs before the frozen time. y is the number of submissions aer or exact at the frozen time. If x = 0, print "0/y" instead of "-0/y".

  After the initial score board, print the process of the unfreeze procedure. During the unfreeze procedure, every time one team unfreezes one frozen problem and causes the change of its rank, print "Name1 Name2 Solved Penalty". Suppose this team is team A. Name1 is the name of team A. Name2 is the name of the team which is overtaken by team A with the highest rank. Solved is the new number of the solved problems of team A. Penalty is the new penalty time of team A.
  Finally print the final score board (after the unfreeze procedure) as the same format as the initial score board.
  See the sample to get more details.

Sample Input

1 20 12 300 240 Epic B 12 YES Epic A 14 NO Rivercrab E 25 YES Two2erII B 100 NO Epic A 120 YES Rivercrab I 150 NO Two2erII C 160 NO Epic C 180 YES Two2erII C 180 NO Rivercrab F 226 YES Two2erII C 230 YES Two2erII L 241 YES Epic F 246 YES Epic G 260 YES Rivercrab I 289 YES Epic D 297 YES Musou H 299 YES Musou I 299 YES Musou J 299 YES Musou K 299 YES

Sample Output

Case #1: Epic 1 3 332 +1 + + 0/1 . 0/1 0/1 . . . . . Rivercrab 2 2 251 . . . . + + . . -1/1 . . . Two2erII 3 1 270 . -1 +2 . . . . . . . . 0/1 Musou 4 0 0 . . . . . . . 0/1 0/1 0/1 0/1 . Musou Two2erII 2 598 Two2erII Musou 2 511 Musou Rivercrab 3 897 Rivercrab Musou 3 560 Musou Epic 4 1196 Epic Musou 4 629 Epic 1 6 1135 +1 + + + . + + . . . . . Musou 2 4 1196 . . . . . . . + + + + . Rivercrab 3 3 560 . . . . + + . . +1 . . . Two2erII 4 2 511 . -1 +2 . . . . . . . . +

Hint

Source

2013 Asia Chengdu Regional Contest

提交代码