102222: [AtCoder]ABC222 C - Swiss-System Tournament

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $300$ points

Problem Statement

$2N$ players, with ID numbers $1$ through $2N$, will participate in a rock-scissors-paper contest.

The contest has $M$ rounds. Each round has $N$ one-on-one matches, where each player plays in one of them.

For each $i=0, 1, \ldots, M$, the players' ranks at the end of the $i$-th round are determined as follows.

  • A player with more wins in the first $i$ rounds ranks higher.
  • Ties are broken by ID numbers: a player with a smaller ID number ranks higher.

Additionally, for each $i=1, \ldots, M$, the matches in the $i$-th round are arranged as follows.

  • For each $k=1, 2, \ldots, N$, a match is played between the players who rank $(2k-1)$-th and $2k$-th at the end of the $(i-1)$-th round.

In each match, the two players play a hand just once, resulting in one player's win and the other's loss, or a draw.

Takahashi, who can foresee the future, knows that Player $i$ will play $A_{i, j}$ in their match in the $j$-th round, where $A_{i,j}$ is G, C, or P.
Here, G stands for rock, C stands for scissors, and P stands for paper. (These derive from Japanese.)

Find the players' ranks at the end of the $M$-th round.

Rules of rock-scissors-paper The result of a rock-scissors-paper match is determined as follows, based on the hands played by the two players.
  • If one player plays rock (G) and the other plays scissors (C), the player playing rock (G) wins.
  • If one player plays scissors (C) and the other plays paper (P), the player playing scissors (C) wins.
  • If one player plays paper (P) and the other plays rock (G), the player playing paper (P) wins.
  • If the players play the same hand, the match is drawn.

Constraints

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

Input

Input is given from Standard Input in the following format:

$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}$

Output

Print $2N$ lines.

The $i$-th line should contain the ID number of the player who ranks $i$-th at the end of the $M$-th round.


Sample Input 1

2 3
GCP
PPP
CCC
PPC

Sample Output 1

3
1
2
4

In the first round, matches are played between Players $1$ and $2$, and between Players $3$ and $4$. Player $2$ wins the former, and Player $3$ wins the latter.
In the second round, matches are played between Players $2$ and $3$, and between Players $1$ and $4$. Player $3$ wins the former, and Player $1$ wins the latter.
In the third round, matches are played between Players $3$ and $1$, and between Players $2$ and $4$. Player $3$ wins the former, and Player $4$ wins the latter.
Therefore, in the end, the players are ranked in the following order: $3,1,2,4$, from highest to lowest.


Sample Input 2

2 2
GC
PG
CG
PP

Sample Output 2

1
2
3
4

In the first round, matches are played between Players $1$ and $2$, and between Players $3$ and $4$. Player $2$ wins the former, and Player $3$ wins the latter.
In the second round, matches are played between Players $2$ and $3$, and between Players $1$ and $4$. The former is drawn, and Player $1$ wins the latter.
Therefore, in the end, the players are ranked in the following order: $1,2,3,4$, from highest to lowest.

Input

题意翻译

有 $2n$ 个人玩剪刀石头布。 告诉你每一轮出的手势,然后执行 $m$ 次下面的操作: + 首先,$2i$ 和 $2i-1$ 两个人进行比赛。 + 然后按照胜利的场数第一关键字,编号第二关键字进行排序。 游戏规则: + 如果两个人出的手势相同那么平局。 + 否则,$G$ 可以赢 $C$,$C$ 可以赢 $P$,$P$ 可以赢 $G$。 最后问第 $i$ 名是几号。 $1\le n\le 50$,$1\le m\le 100$。

Output

分数:300分

问题描述

编号为$1$到$2N$的$2N$名选手将参加一场石头-剪刀-布比赛。

比赛共有$M$轮。每轮有$N$场一对一的比赛,每名选手参加其中一场。

对于每个$i=0, 1, \ldots, M$,在第$i$轮结束时,玩家的排名如下确定。

  • 在前$i$轮中获胜次数较多的玩家排名更高。
  • 平局由ID号码决定:ID号码较小的玩家排名更高。

此外,对于每个$i=1, \ldots, M$,第$i$轮的比赛如下安排。

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

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

能够预见未来的高桥知道,第$i$名玩家将在第$j$轮的比赛中玩$A_{i, j}$,其中$A_{i,j}$是GCP

找到在第$M$轮结束时玩家的排名。

石头-剪刀-布的规则 石头-剪刀-布比赛的结果如下,基于两名玩家玩的手。
  • 如果一名玩家玩石头(G)而另一名玩家玩剪刀(C),则玩石头(G)的玩家获胜。
  • 如果一名玩家玩剪刀(C)而另一名玩家玩纸(P),则玩剪刀(C)的玩家获胜。
  • 如果一名玩家玩纸(P)而另一名玩家玩石头(G),则玩纸(P)的玩家获胜。
  • 如果玩家玩相同的手,比赛平局。

约束条件

  • $1 \leq N \leq 50$
  • $1 \leq M \leq 100$
  • $A_{i,j}$是GCP

输入

输入格式如下,从标准输入给出:

$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$的玩家的ID号。


样例输入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$,从高到低。

加入题单

上一题 下一题 算法标签: