JSUTC202004 B

2020年4月8日

JSUTC202004 B

さて,前回に引き続きJSUTC202004 の B 問題を解説していきます。
今回は参加人数が少なくて,そのこともあってか処理速度がめちゃくちゃ速くなっててかなり驚きました(笑)。
ほんとに流石です。
では,解説していきます。
https://atcoder.jp/contests/judge-update-202004/tasks/judge_update_202004_b

B – Picking Balls


実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200 点

問題文

赤か青で塗られた N 個のボールが入った袋があります。また、それぞれのボールには整数が書かれています。

i 個目のボールには整数 Xi が書かれており、色は Ci が R のとき赤、B のとき青です。

高橋君は、袋の中にボールが残っている間、次の手順を繰り返して袋からボールを取り出します。

  • 袋の中に赤のボールがあるとき、残っている赤のボールのうち最小の整数が書かれたボールを袋から取り出す。そうでないとき、残っている青のボールのうち最小の整数が書かれたボールを袋から取り出す。

高橋君が各手順で取り出したボールに書かれていた整数を求めてください。

制約

  • 1≤N≤100
  • 1≤Xi≤10000
  • Ci は R または B
  • Xi≠Xj(i≠j)
  • N,Xi は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
X1 C1
X2 C2
:
XN CN

出力

高橋君が各手順で取り出したボールに書かれていた整数を出力せよ。

解説

袋の中に赤のボールが残っていればそのうちの最小の整数を出していき,赤のボールがなくなれば,今度は青いボールのなかの最小の整数を出していくということなので,結局赤いボールを小さい順に出力した後,青いボールを小さい順に出力してあげれば良いわけです。
そのためにまずボールに書かれている整数を昇順にソートした後に,RかBかでソートすればいいわけです。

解答

n = int(input())
# X,C の入力値をリストにして,それを a というリストに格納
a = []
for i in range(n):
    a.append(input().split())
    a[i][0] = int(a[i][0])

# 数値の昇順にソート
a.sort(key=lambda  x: x[0])

# R か B かでソートし,R が先に出るように降順でソート
a.sort(key=lambda  x: x[1] , reverse=True)

for i in range(n):
    print(a[i][0])