#1187073 (PyPy3) No.3749 Three Jugs

• 問題: No.3749 Three Jugs
• ユーザー: Naru820
• 提出日時: 2026-09-16 20:58:23
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 4,093 ms / 5,000 ms
• コード長: 6,745 bytes
• コンパイル時間: 87 ms
• コンパイル使用メモリ: 82,916 KB
• 実行使用メモリ: 109,860 KB
• 最終ジャッジ日時: 2026-09-25 20:55:27
• 合計ジャッジ時間: 45,561 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 23

ソースコード

import sys

input = sys.stdin.readline

INF = 1 << 62


def solve(cap, s, t):
    water = sum(s)

    for i in range(3):
        if min(s[i], t[i]) < 0 or max(s[i], t[i]) > cap[i]:
            return -1

    if water != sum(t):
        return -1

    def boundary(v):
        cnt = 0
        for i in range(3):
            cnt += v[i] == 0 or v[i] == cap[i]
        return cnt

    if s == t:
        return 0

    if not boundary(t):
        return -1

    # start[0] = s
    # start[1:] = s から1回で到達できる状態
    start = [s]

    for i in range(3):
        for j in range(3):
            if i == j:
                continue

            v = list(s)
            d = min(v[i], cap[j] - v[j])
            v[i] -= d
            v[j] += d
            v = tuple(v)

            if v == t:
                return 1

            start.append(v)

    if boundary(t) >= 2:
        return 2

    order = [[], []]
    length = []
    weight = []
    cost = []

    n = 0
    keep = 0

    for i in range(3):
        for j in range(3):
            if i == j or cap[i] == 0 or cap[j] == 0:
                continue

            k = 3 - i - j

            lo = max(0, water - cap[i] - cap[j] + 1)
            hi = min(cap[k], water - 1)

            if lo > hi:
                continue

            cuts = [lo, hi + 1]

            def cut(z):
                if lo <= z <= hi:
                    cuts.append(z)
                    cuts.append(z + 1)

            for z in (
                0,
                cap[k],
                water - cap[i],
                water - cap[j],
            ):
                cut(z)

            # start のうち、この i -> j の列に実際に属するものだけ分離
            for v in start:
                if v[i] == cap[i] or v[j] == 0:
                    cut(v[k])

            # t がこの列に現れ得る場合だけ分離
            if (
                t[i] == 0
                or t[i] == cap[i]
                or t[j] == 0
                or t[j] == cap[j]
            ):
                cut(t[k])

            cuts.sort()

            for p in range(1, len(cuts)):
                for rev in range(2):
                    if cuts[p] == cuts[p - 1]:
                        continue

                    sign = 1 - 2 * rev
                    z = cuts[p] - 1 if rev else cuts[p - 1]

                    u = [0, 0, 0]
                    v = [0, 0, 0]

                    u[k] = v[k] = z

                    # u --(i -> j)--> v
                    u[i] = min(cap[i], water - z)
                    u[j] = water - z - u[i]

                    v[j] = min(cap[j], water - z)
                    v[i] = water - z - v[j]

                    u = tuple(u)
                    v = tuple(v)

                    # v から次に行く操作
                    ni = j
                    nj = i

                    if boundary(v) == 1:
                        if v[i] == 0:
                            ni = k
                            nj = i
                        else:
                            ni = j
                            nj = k

                    idx = n
                    n += 1

                    # 通常順・逆順を合わせて、
                    # 始点側と終点側で対応する辺の順序をそろえる
                    order[0].append((
                        u != t,
                        3 * i + j + 9 * rev,
                        sign * z,
                        idx,
                    ))

                    order[1].append((
                        v != t,
                        3 * ni + nj + 9 * (1 - rev),
                        -sign * v[3 - ni - nj],
                        idx,
                    ))

                    length.append(cuts[p] - cuts[p - 1])
                    weight.append(1)

                    # この辺の始点 u までの既知の最短距離
                    best = 2 if boundary(u) >= 2 else INF

                    for h, x in enumerate(start):
                        if u == x:
                            best = min(best, int(h != 0))

                    cost.append(best)

                    if u == t:
                        keep += 1

    row = [[], []]

    for side in range(2):
        order[side].sort()
        row[side] = [x[3] for x in order[side]]

    # t のコピー以外をすべて縮約する
    while len(row[0]) > keep:
        win = row[0][-1]
        lose = row[1][-1]

        if win == lose:
            row[0].pop()
            row[1].pop()
            continue

        # 本数の多い側を勝者にする
        side = int(length[win] < length[lose])
        win = row[side][-1]

        other = row[side ^ 1]

        # C++ の first は「other 内の win の直後」
        first = len(other)
        total = 0

        while other[first - 1] != win:
            first -= 1
            total += length[other[first]]

        last = len(other)

        # 勝者より後ろを何周できるか
        q = length[win] // total
        length[win] %= total

        # q 周した後、さらに末尾側からどこまで処理できるか
        mid = last

        while (
            mid != first
            and length[win] >= length[other[mid - 1]]
        ):
            mid -= 1
            length[win] -= length[other[mid]]

        # q 周分 + 端数分をまとめて反映
        begin = first if q else mid

        for pos in range(begin, last):
            rounds = q + int(pos >= mid)
            lose = other[pos]

            if side:
                cost[lose] = min(
                    cost[win],
                    rounds * weight[win] + cost[lose],
                )
            else:
                cost[lose] = min(
                    cost[lose],
                    weight[lose] + cost[win],
                )

            weight[lose] += rounds * weight[win]

        # rotate(first, mid, last)
        #
        # [first:mid][mid:last]
        #      ↓
        # [mid:last][first:mid]
        if first != mid and mid != last:
            other[first:last] = (
                other[mid:last] + other[first:mid]
            )

        if length[win] == 0:
            row[side].pop()

            # win 自身は first の1つ前にある
            del other[first - 1]

    ans = INF

    for idx in row[0]:
        ans = min(ans, cost[idx])

    return -1 if ans == INF else ans


def main():
    T = int(input())
    out = []

    for _ in range(T):
        A = tuple(map(int, input().split()))
        B = tuple(map(int, input().split()))
        C = tuple(map(int, input().split()))

        out.append(str(solve(A, B, C)))

    print("\n".join(out))


if __name__ == "__main__":
    main()