AtCoder-ABC213 C - Reorder Cards【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210808231336p:plain

AtCoder Beginner Contest213のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 213 - AtCoder

AtCoder Beginner Contest213 C - Reorder Cards

問題文

H 行 W 列の格子状に HW 枚のカードが並べられています。i=1,…,N について、上から Ai 行目、左から Bi 列目にあるカードには数 i が書かれており、それ以外の HW−N 枚のカードには何も書かれていません。

これらのカードに対し、以下の 2 種類の操作を可能な限り繰り返します。

・数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
・数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める
操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。なお、答えは操作の仕方に依らず一意に定まることが証明されます。

制約

・1 ≤ H,W ≤ 10^9
・1 ≤ N ≤ min( 10 ^ 5 , HW)
・1 ≤ Ai ≤ H
・1 ≤ Bi ≤ W
・(Ai , Bi) は相異なる
・入力に含まれる値は全て整数である

解答例

import bisect

h, w, n = map(int,input().split())

A = []
B = []
for i in range(n):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)

X = list(set(A))
X.sort()
Y = list(set(B))
Y.sort()

for i in range(n):
    C = bisect.bisect_left(X, A[i]) + 1
    D = bisect.bisect_left(Y, B[i]) + 1
    print(str(C) + " " + str(D))