| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 4 | 2 | 2 | 66.667% |
The legend, example, and note of this problem are used fictitiously. Any resemblance to the actual contests, rules, submissions, or teams is coincidental.
In the International Challenging Puzzle Contest (ICPC), there are $m$ submissions. You are given the list of $m$ submissions ordered by time. A submission can be represented as a tuple $(c,p,t,s),ドル which means team $c$ makes a submission on problem $p$ at time $t$ with status $s$. The status of a submission is either "accepted" or "rejected".
The score of a team is the pair of the number of problems solved by the team and the total time consumed$^\dagger$ by the team. The larger the number of problems solved is, the higher the score is. If a tie occurs, the smaller the total time consumed is, the higher the score is.
If team $c$ makes at least one submission with status "accepted" on problem $p,ドル we say that team $c$ solves problem $p$. A team can get a gold medal if the number of teams with higher score is less than $\min(\lceil 0.1 \cdot n \rceil, 35),ドル where $n$ is the number of teams that solved at least one problem and $\lceil x \rceil$ denotes the smallest integer that is not smaller than $x$.
You need to find all the teams that can get a gold medal if at most one of the $m$ submissions changes its status.
$\dagger$ The total time consumed is the sum of times consumed for all solved problems (0ドル$ if no problems are solved). The time consumed for a solved problem is the time of the first submission with status "accepted", plus 20ドル$ times the number of submissions on this problem before the first submission with status "accepted". Note that we say submission $i$ is before submission $j$ if and only if submission $i$ appears earlier than submission $j$ in the given list of $m$ submissions.
Each test contains multiple test cases. The first line contains a single integer $t$ (1ドル \le t \le 10^5$) denoting the number of test cases. For each test case:
The first line contains a single integer $m$ (1ドル \le m \le 10^5$) denoting the number of submissions.
The $i$-th of the following $m$ lines contains $c_i,ドル $p_i,ドル $t_i,ドル and $s_i$ which mean that team $c_i$ makes a submission on problem $p_i$ at time $t_i$ with status $s_i$. Specifically:
_'). Note that no two teams have the same name.accepted" or "rejected".It is guaranteed that $t_i \le t_j$ for all $i < j$. Recall that if $t_i = t_j$ and $i < j,ドル we still say that the $i$-th submission came before the $j$-th submission.
It is guaranteed that the sum of $m$ over all test cases does not exceed 10ドル^5$.
For each test case:
Output one integer $k$ on the first line, denoting the number of teams that can get a gold medal if at most one of the $m$ submissions changes its status.
On the second line, output $k$ distinct strings in any order, denoting the names of these $k$ teams.
2 5 TSxingxing10 G 0 rejected TSxingxing10 B 83 accepted aoliaoligeiliao J 98 accepted TS1 J 118 accepted TS1 B 263 accepted 12 AllWayTheNorth A 0 rejected YaoYaoLingXian Y 10 accepted XuejunXinyoudui1 X 200 rejected XuejunXinyoudui1 X 200 accepted LetItRot L 215 accepted AllWayTheNorth W 250 accepted ImYourFan I 257 accepted ImYourFan Y 257 accepted AllWayTheNorth T 264 accepted XuejunXinyoudui1 J 294 accepted LetItRot I 299 accepted LetItRot I 299 rejected
2 TSxingxing10 TS1 4 AllWayTheNorth XuejunXinyoudui1 LetItRot ImYourFan
2 2 jiangly_fan A 1 accepted jiangly B 23 accepted 3 conqueror_of_tourist A 1 accepted conqueror_of_tourist A 2 accepted tourist B 23 accepted
2 jiangly_fan jiangly 1 conqueror_of_tourist
2 13 A A 1 accepted A X 1 accepted K K 1 rejected B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 accepted H H 2 accepted I I 2 accepted J J 2 accepted K K 2 rejected 12 A A 1 accepted A X 1 accepted B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 accepted H H 2 accepted I I 2 accepted J J 2 rejected K K 2 rejected
11 A K B C D E F G H I J 1 A
2 11 A A 1 accepted B B 1 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 accepted H H 2 accepted I I 2 accepted J J 2 accepted K K 2 accepted 12 A A 1 accepted A X 1 accepted K K 1 rejected B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 accepted H H 2 accepted I I 2 accepted J J 2 accepted
2 A B 2 A K
In the first case of the first example, TS1 solves two problems, so they can get a gold medal. TSxingxing10 can get a gold medal if their first submission changes its status to "accepted".
In the second case of the first example, AllWayTheNorth, XuejunXinyoudui1, LetItRot and ImYourFan have the same score, two problems solved with 514ドル$ total time consumed. They can get gold medals simultaneously if no submission changes its status.