首页 > ACM题库 > HDU-杭电 > hdu 4789 ICPC Ranking待解决[解题报告]C++
2015
09-18

hdu 4789 ICPC Ranking待解决[解题报告]C++

ICPC Ranking

问题描述 :

  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.

输入:

  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.

输出:

  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.

样例输入:

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

样例输出:

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 . . . . . . . . +