又到年终总结时,某科技公司决定评选一批优秀项目团队,发放年终特别奖。公司规定,奖项分为三类:卓越奖(A类)、优胜奖(B类) 和 进步奖(C类)。
公司共有 N 支项目团队参与评选。每支团队来自一个部门,每个部门可能有多个团队参选。
公司已经收到所有团队的参选数据,数据包括:部门名称、小组名称、完成项目数、完成项目总耗时。
不过,在评选奖项时,公司发现部分团队有项目超时完成 或 虽然还未超时但目前尚未完成任何项目,因此这些团队不具有参选资格。
*,说明该团队有项目超时完成,取消该团队的参选资格。所有有资格参选的团队,我们称为有效参选团队。
设有效参选团队总数为 Cnt:
现给出所有报名参选团队的数据,并给出一个字符(A 或 B 或 C)表示询问的奖项类别,请按照排序后的结果,输出获得该类奖项团队的数据。
第一行一个整数 N,表示团队数量。
接下来 N 行,每行依次包含:团队隶属部门名称、团队名称、完成项目数、完成项目总时间。
最后一行输入一个字符(A 或 B 或 C),表示询问的奖项类别。
第一行输出一个整数 res,代表获得该类奖项的团队数量。
接下来的 res 行,输出按评选规则排序后,获得该类奖项的团队的信息,每行依次输出:团队隶属部门名称、团队名称、完成项目数、完成项目总时间。
6 deptA team1 5 100 deptB team2* 6 90 deptC team3 4 110 deptD team4 6 80 deptE team5 3 95 deptF team6 6 70 A
1 deptF team6 6 70
13 a a1 5 150 b b1* 5 140 c c1 4 160 d d1 4 155 e e1 3 170 f f1 2 180 g g1 3 190 h h1 2 200 i i1 4 145 j j1 1 210 k k1 4 148 l l1 2 175 m m1* 5 125 C
3 c c1 4 160 e e1 3 170 g g1 3 190
27 a a1 6 200 b b1* 5 150 c c1 6 140 d d1 5 160 e e1 4 170 f f1 6 130 g g1 5 135 h h1 6 110 i i1 5 105 j j1* 4 115 k k1 3 145 l l1 2 150 m m1 4 125 n n1 6 90 o o1 4 180 p p1 5 195 q q1 4 185 r r1 6 100 s s1 2 175 t t1 1 160 u u1 3 200 v v1 5 190 w w1 3 215 x x1* 5 220 y y1 6 95 z z1 4 98 zz zz1 6 91 B
5 r r1 6 100 h h1 6 110 f f1 6 130 c c1 6 140 a a1 6 200
有效团队共 5 个,A 类获奖名额为 ceil(5 \times 10\%) = 1。获得该类奖项的 1 个团队来自 deptF 部门,团队名称为 team6。
对于所有数据,满足:1 \leq N \leq 2 \times 10^5,部门名称、团队名称仅由英文的小写字母和 * 组成,且长度不超过 30 个字符,所有团队完成项目数在 [0, 20] 的范围内,所有团队完成项目的总时间在 [0, 2^{31} - 1] 的范围内且所有团队完成项目的总时间互不相同。
| 测试点编号 | 特殊性质 |
|---|---|
| 15\% 的数据 | A |
| 另外 50\% 的数据 | B |
特殊性质A:保证所有团队完成项目数互不相同,且已经按照完成项目数降序排序。
特殊性质B:保证询问的获奖类别一定是 A 类。