Swiss-System Tournament

题目描述

$2N$ 名选手，编号为 $1$ 到 $2N$，将参加石头剪刀布比赛。 比赛共有 $M$ 轮。每一轮有 $N$ 场一对一的对战，每位选手参加其中的一场。 对于每个 $i=0,1,\ldots,M$，第 $i$ 轮结束时的选手排名按如下方式决定。

在前 $i$ 轮中胜场更多的选手排名更高。 平局按编号决定：编号较小的选手排名更高。

此外，对于每个 $i=1,\ldots,M$，第 $i$ 轮的对阵按如下方式安排。

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

在每场比赛中，两名选手各出一手，仅进行一次，结果为一方胜一方负，或平局。 能够预见未来的高桥知道选手 $i$ 在第 $j$ 轮的比赛中将出 $A_{i,j}$，其中 $A_{i,j}$ 是 $G$、$C$ 或 $P$。
这里，$G$ 代表石头，$C$ 代表剪刀，$P$ 代表布。（这些来自日语。） 求第 $M$ 轮结束时选手的排名。

输入格式

输入按照下述格式由标准输入给出： $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$ 行应当包含第 $M$ 轮结束时排名第 $i$ 位的选手的编号。

2 3
GCP
PPP
CCC
PPC

3
1
2
4

2 2
GC
PG
CG
PP

1
2
3
4

提示

$1 \leq N \leq 50$ $1 \leq M \leq 100$ $A_{i,j}$ 是 $G$、$C$ 或 $P$。在第一轮，比赛在选手 $1$ 和 $2$ 之间进行，以及在选手 $3$ 和 $4$ 之间进行。选手 $2$ 赢得前者，选手 $3$ 赢得后者。
在第二轮，比赛在选手 $2$ 和 $3$ 之间进行，以及在选手 $1$ 和 $4$ 之间进行。选手 $3$ 赢得前者，选手 $1$ 赢得后者。
在第三轮，比赛在选手 $3$ 和 $1$ 之间进行，以及在选手 $2$ 和 $4$ 之间进行。选手 $3$ 赢得前者，选手 $4$ 赢得后者。
因此，最终选手的排名从高到低依次为：$3,1,2,4$。
在第一轮，比赛在选手 $1$ 和 $2$ 之间进行，以及在选手 $3$ 和 $4$ 之间进行。选手 $2$ 赢得前者，选手 $3$ 赢得后者。
在第二轮，比赛在选手 $2$ 和 $3$ 之间进行，以及在选手 $1$ 和 $4$ 之间进行。前者为平局，选手 $1$ 赢得后者。
因此，最终选手的排名从高到低依次为：$1,2,3,4$。

标签: AtCoder|abc222C

来源

AtCoder|abc222C