#1187070 (PyPy3) No.3749 Three Jugs

• 問題: No.3749 Three Jugs
• ユーザー: Naru820
• 提出日時: 2026-09-16 20:54:15
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 5,568 bytes
• コンパイル時間: 85 ms
• コンパイル使用メモリ: 82,388 KB
• 実行使用メモリ: 147,584 KB
• 最終ジャッジ日時: 2026-09-25 20:53:35
• 合計ジャッジ時間: 17,256 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_0

ファイルパターン	結果
sample	-- * 1
other	TLE * 1 -- * 22

ソースコード

import sys

input = sys.stdin.readline

INF = 1 << 62


def solve(A, B, C):
    W = sum(B)

    def boundary(x):
        return sum(x[i] == 0 or x[i] == A[i] for i in range(3))

    if B == C:
        return 0

    if not boundary(C):
        return -1

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

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

            x = list(B)
            d = min(x[i], A[j] - x[j])
            x[i] -= d
            x[j] += d
            x = tuple(x)

            if x == C:
                return 1

            start.append(x)

    if boundary(C) >= 2:
        return 2

    # -1: C
    #  0: B
    #  1: Bから1回
    #  2: 頂点
    #  3: それ以外
    def mark(x):
        x = tuple(x)

        if x == C:
            return -1
        if x == B:
            return 0

        for y in start:
            if x == y:
                return 1

        return 2 if boundary(x) >= 2 else 3

    # id ごとの
    # len[id]    : 辺の本数
    # weight[id] : 辺1本が表す操作回数
    length = []
    weight = []
    initial = []

    # 始点側・終点側から見た並び
    order = [[], []]

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

            k = 3 - i - j

            lo = max(0, W - A[i] - A[j] + 1)
            hi = min(A[k], W - 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,
                A[k],
                W - A[i],
                W - A[j],
                B[k],
                C[k],
            ):
                cut(z)

            for x in start:
                cut(x[k])

            cuts.sort()

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

                    # r=0: 通常順
                    # r=1: 逆順
                    z = cuts[p + 1] - 1 if r else cuts[p]
                    sign = 1 - 2 * r

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

                    u[k] = v[k] = z

                    # u --(i -> j)--> v
                    u[i] = min(A[i], W - z)
                    u[j] = W - z - u[i]

                    v[j] = min(A[j], W - z)
                    v[i] = W - z - v[j]

                    # v から次に行う操作 ni -> nj
                    ni = j
                    nj = i

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

                    idx = len(length)

                    order[0].append((
                        mark(u) == 3,
                        9 * r + 3 * i + j,
                        sign * z,
                        idx,
                    ))

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

                    length.append(cuts[p + 1] - cuts[p])
                    weight.append(1)
                    initial.append(mark(u))

    row = [[], []]

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

    # 印・目標は先頭に集まっている
    dist = []

    for idx in row[0]:
        if initial[idx] != 3:
            dist.append(initial[idx])

    # 印・目標以外を縮約する
    while len(row[0]) > len(dist):
        a = row[0][-1]
        b = row[1][-1]

        if a == b:
            row[0].pop()
            row[1].pop()
            continue

        # 本数が多い方を勝者にする
        side = int(length[a] < length[b])
        win = row[side][-1]

        other = row[side ^ 1]
        pos = other.index(win)

        # win より後ろにあるグループの本数
        total = 0
        for idx in other[pos + 1:]:
            total += length[idx]

        q = length[win] // total

        if q:
            # 一巡分をまとめて処理
            length[win] %= total

            for idx in other[pos + 1:]:
                weight[idx] += q * weight[win]

        else:
            lose = other[-1]

            # s --lose--> v --win--> t を縮約
            length[win] -= length[lose]
            weight[lose] += weight[win]

            # lose を win の直後へ移す
            other[pos + 1:] = [other[-1]] + other[pos + 1:-1]

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

    ans = INF

    # 最後は印と目標だけが残る
    for i in range(len(dist)):
        if dist[i] != -1:
            continue

        # C に入る圧縮済みの辺
        idx = row[1][i]

        # その辺の始点
        p = row[0].index(idx)

        if dist[p] >= 0:
            ans = min(ans, weight[idx] + dist[p])

    return -1 if ans == INF else ans


def main():
    T = int(input())

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

        print(solve(A, B, C))


if __name__ == "__main__":
    main()