← 返回题目列表

AtCoder · abc222_c

E. 瑞士系统锦标赛

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

2N 玩家,带有 ID 号 1 通过 2N,将参加石头剪刀布大赛。

比赛有 M 回合。每轮有 N 一对一比赛,每个玩家参加其中一场比赛。

对于每个 i=0, 1, \ldots, M,最后玩家的排名 i第轮确定如下。

  • 第一位人数较多的玩家获胜 i 回合排名更高。
  • 平局是通过 ID 号来打破的:ID 号越小的玩家排名越高。

此外,对于每个 i=1, \ldots, M,匹配项 i第轮安排如下。

  • 对于每个 k=1, 2, \ldots, N,在排名的玩家之间进行一场比赛 (2k-1)-th 和 2k- 结束时 (i-1)-第轮。

在每场比赛中,两名玩家只玩一手牌,导致一名玩家获胜,另一名玩家失败,或者平局。

能够预见未来的高桥知道,玩家 i 将播放 A_{i, j} 在他们的比赛中 j第一轮,其中 A_{i,j} is G, C,或 P.
在这里, G 代表摇滚, C 代表剪刀,并且 P 代表纸张。 (这些源自日语。)

查找最后玩家的排名 M-第轮。

石头剪刀布的规则 石头剪刀布比赛的结果根据两名玩家所打的手牌确定如下。
  • 如果一名玩家玩石头 (G),另一名玩家玩剪刀 (C),则玩石头 (G) 的玩家获胜。
  • 如果一名玩家玩剪刀 (C),另一名玩家玩布 (P),则玩剪刀 (C) 的玩家获胜。
  • 如果一名玩家玩纸 (P),另一名玩家玩石头 (G),则玩纸 (P) 的玩家获胜。
  • 如果玩家打同一手牌,则比赛平局。

约束

  • 1 \leq N \leq 50
  • 1 \leq M \leq 100
  • A_{i,j} is G, C,或 P.

输入

输入由标准输入按以下格式给出:

N M
A_{1,1}A_{1,2}\ldots A_{1,M}
A_{2,1}A_{2,2}\ldots A_{2,M}
\vdots
A_{2N,1}A_{2N,2}\ldots A_{2N,M}

输出

打印 2N 行。

的 i-第行应包含排名玩家的ID号 i- 结束时 M-第轮。


示例输入 1

2 3
GCP
PPP
CCC
PPC

示例输出 1

3
1
2
4

第一轮比赛在玩家之间进行 1 和 2,以及玩家之间 3 和 4。玩家 2 赢得前者,而玩家 3 赢得了后者。
第二轮比赛在玩家之间进行 2 和 3,以及玩家之间 1 和 4。玩家 3 赢得前者,而玩家 1 赢得了后者。
第三轮,玩家之间进行比赛 3 和 1,以及玩家之间 2 和 4。玩家 3 赢得前者,而玩家 4 赢得了后者。
因此,最终选手的排名顺序如下: 3,1,2,4,从最高到最低。


示例输入 2

2 2
GC
PG
CG
PP

示例输出 2

1
2
3
4

第一轮比赛在玩家之间进行 1 和 2,以及玩家之间 3 和 4。玩家 2 赢得前者,而玩家 3 赢得了后者。
第二轮比赛在玩家之间进行 2 和 3,以及玩家之间 1 和 4。前者已抽出,而玩家 1 赢得了后者。
因此,最终选手的排名顺序如下: 1,2,3,4,从最高到最低。