D - Reconstruct Chocolate https://atcoder.jp/contests/abc445/tasks/abc445_d

abc445_d.py

from collections import deque, defaultdict

H, W, N = map(int, input().split())
h2i = defaultdict(list)         # 高さhのピースのインデックスを管理
w2i = defaultdict(list)         # 幅wのピースのインデックスを管理
pieces = []
for i in range(N):
    h, w = map(int, input().split())
    pieces.append((h, w))
    h2i[h].append(i)
    w2i[w].append(i)


used = [False] * N
que = deque()
if H in h2i:
    for idx in h2i[H]:
        if not used[idx]:
            used[idx] = True
            que.append(idx)

if W in w2i:
    for idx in w2i[W]:
        if not used[idx]:
            used[idx] = True
            que.append(idx)

x_s, y_s = 0, 0
ans = [None] * N
while que:
    idx = que.popleft()
    if ans[idx] is not None:
        continue
    hi, wi = pieces[idx]
    if hi == H:
        W -= wi
        ans[idx] = (y_s + 1, x_s + 1)
        x_s += wi
        if W in w2i:
            for nxt_idx in w2i[W]:
                if not used[nxt_idx]:
                    used[nxt_idx] = True
                    que.append(nxt_idx)
    elif wi == W:
        H -= hi
        ans[idx] = (y_s + 1, x_s + 1)
        y_s += hi
        if H in h2i:
            for nxt_idx in h2i[H]:
                if not used[nxt_idx]:
                    used[nxt_idx] = True
                    que.append(nxt_idx)


for i in range(N):
    print(*ans[i])