DEGwer さんの D 論応援コンテスト B問題メモ

class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def save(self):
        self.saved = self.table.copy()

    def restore(self):
        self.table = self.saved

    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return False
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
        return True

    def get_size(self, x):
        return -self.table[self.root(x)]


def check(spt0, uft0: UnionFind, spt1):
    uft0.save()
    for u, v in spt0:
        uft0.unite(u, v)

    roots = [u for u, val in enumerate(uft0.table) if val < 0]
    if len(roots) == 1:
        uft0.restore()
        if len(spt0) > len(spt1):
            return next(iter(spt0))
        else:
            return next(iter(spt1))

    for u, v in spt1:
        if not uft0.find(u, v):
            uft0.restore()
            return (u, v)


h, w, move = input().split()
h = int(h)
w = int(w)

if h <= w:
    print('No')
    exit()

if h == w + 1 and move == 'Second':
    print('No')
    exit()

print('Yes')

n = h * w + 2
s = h * w
t = s + 1
spt = [set(), set()]
uft = [UnionFind(n), UnionFind(n)]
for i in range(h):
    b = i & 1
    spt[b].add((s, i * w))
    b ^= 1
    for j in range(w - 1):
        spt[b].add((i * w + j, i * w + j + 1))
        b ^= 1
    spt[b].add(((i + 1) * w - 1, t))
    if i < h - 1:
        b = (i & 1)
        for j in range(w):
            spt[b].add((i * w + j, (i + 1) * w + j))
            b ^= 1

if move == 'First':
    print('- 1 1')
    uft[0].unite(0, w)
    uft[1].unite(0, w)
    spt[0].discard((0, w))
    spt[1].discard((0, w))

while True:
    op, di, dj = input().split()
    if op == 'a' or op == 'w':
        break

    di = int(di) - 1
    dj = int(dj) - 1
    if op == '|':
        if dj == 0:
            closed = (s, di * w)
        elif dj == w:
            closed = ((di + 1) * w - 1, t)
        else:
            closed = (di * w + dj - 1, di * w + dj)
    else:
        closed = (di * w + dj, (di + 1) * w + dj)

    if closed in spt[0]:
        spt[0].remove(closed)
        u, v = opened = check(spt[0], uft[0], spt[1])
    else:
        spt[1].remove(closed)
        u, v = opened = check(spt[1], uft[1], spt[0])

    if u == s:
        print(f'| {v // w + 1} 1')
    elif v == t:
        print(f'| {u // w + 1} {w + 1}')
    elif u + w == v:
        i, j = divmod(u, w)
        print(f'- {i + 1} {j + 1}')
    else:
        i, j = divmod(u, w)
        print(f'| {i + 1} {j + 2}')

    uft[0].unite(u, v)
    uft[1].unite(u, v)
    spt[0].discard(opened)
    spt[1].discard(opened)