#939394 (PyPy3) No.2594 Mix shake!!

提出ソース

結果

問題	No.2594 Mix shake!!
ユーザー	👑 hitonanode
提出日時	2023-12-20 12:17:24
言語	PyPy3 (7.3.15)
結果	AC
実行時間	185 ms / 2,000 ms
コード長	2,024 bytes
コンパイル時間	212 ms
コンパイル使用メモリ	81,700 KB
実行使用メモリ	88,332 KB
最終ジャッジ日時	2023-12-20 12:17:41
合計ジャッジ時間	15,538 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	131 ms 87,692 KB
testcase_01	AC	135 ms 87,692 KB
testcase_02	AC	130 ms 87,692 KB
testcase_03	AC	131 ms 87,692 KB
testcase_04	AC	137 ms 87,692 KB
testcase_05	AC	137 ms 87,692 KB
testcase_06	AC	139 ms 87,692 KB
testcase_07	AC	140 ms 87,692 KB
testcase_08	AC	139 ms 87,692 KB
testcase_09	AC	139 ms 87,692 KB
testcase_10	AC	132 ms 87,692 KB
testcase_11	AC	137 ms 87,692 KB
testcase_12	AC	141 ms 87,692 KB
testcase_13	AC	132 ms 87,692 KB
testcase_14	AC	133 ms 87,692 KB
testcase_15	AC	131 ms 87,692 KB
testcase_16	AC	131 ms 87,692 KB
testcase_17	AC	136 ms 87,692 KB
testcase_18	AC	133 ms 88,076 KB
testcase_19	AC	142 ms 88,076 KB
testcase_20	AC	143 ms 87,692 KB
testcase_21	AC	146 ms 87,692 KB
testcase_22	AC	139 ms 87,692 KB
testcase_23	AC	137 ms 88,076 KB
testcase_24	AC	130 ms 87,692 KB
testcase_25	AC	130 ms 87,692 KB
testcase_26	AC	131 ms 87,692 KB
testcase_27	AC	131 ms 87,692 KB
testcase_28	AC	130 ms 87,692 KB
testcase_29	AC	147 ms 87,692 KB
testcase_30	AC	139 ms 87,692 KB
testcase_31	AC	139 ms 87,692 KB
testcase_32	AC	147 ms 88,076 KB
testcase_33	AC	144 ms 88,076 KB
testcase_34	AC	182 ms 88,332 KB
testcase_35	AC	178 ms 88,332 KB
testcase_36	AC	183 ms 88,332 KB
testcase_37	AC	175 ms 88,332 KB
testcase_38	AC	183 ms 88,332 KB
testcase_39	AC	182 ms 88,332 KB
testcase_40	AC	179 ms 88,332 KB
testcase_41	AC	176 ms 88,332 KB
testcase_42	AC	175 ms 88,332 KB
testcase_43	AC	175 ms 88,332 KB
testcase_44	AC	185 ms 88,332 KB
testcase_45	AC	166 ms 88,332 KB
testcase_46	AC	173 ms 88,332 KB
testcase_47	AC	175 ms 88,332 KB
testcase_48	AC	178 ms 88,332 KB
testcase_49	AC	176 ms 88,332 KB
testcase_50	AC	180 ms 88,332 KB
testcase_51	AC	168 ms 88,332 KB
testcase_52	AC	175 ms 88,332 KB
testcase_53	AC	175 ms 88,332 KB
testcase_54	AC	135 ms 88,076 KB
testcase_55	AC	134 ms 88,076 KB
testcase_56	AC	131 ms 87,692 KB
testcase_57	AC	137 ms 87,692 KB
testcase_58	AC	166 ms 87,692 KB
testcase_59	AC	136 ms 87,692 KB
testcase_60	AC	134 ms 87,692 KB
testcase_61	AC	134 ms 87,692 KB
testcase_62	AC	133 ms 87,692 KB
testcase_63	AC	139 ms 87,692 KB
testcase_64	AC	139 ms 87,692 KB
testcase_65	AC	151 ms 87,692 KB
testcase_66	AC	147 ms 88,076 KB
testcase_67	AC	143 ms 87,692 KB
testcase_68	AC	143 ms 88,076 KB
testcase_69	AC	135 ms 87,692 KB
testcase_70	AC	138 ms 88,076 KB
testcase_71	AC	136 ms 87,692 KB
testcase_72	AC	132 ms 87,692 KB
testcase_73	AC	131 ms 87,692 KB
testcase_74	AC	161 ms 87,692 KB
testcase_75	AC	131 ms 87,692 KB
testcase_76	AC	134 ms 87,692 KB
testcase_77	AC	129 ms 87,692 KB
testcase_78	AC	130 ms 87,692 KB
testcase_79	AC	131 ms 87,692 KB
testcase_80	AC	135 ms 88,076 KB
testcase_81	AC	133 ms 87,692 KB
testcase_82	AC	166 ms 88,076 KB
testcase_83	AC	135 ms 87,692 KB
testcase_84	AC	138 ms 88,076 KB
testcase_85	AC	135 ms 87,692 KB
testcase_86	AC	135 ms 87,692 KB
testcase_87	AC	138 ms 87,692 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

from fractions import Fraction


def to_slope(vec: list[tuple[Fraction, int, int, int]]) -> list[tuple[int, int]]:
    x, y = 0, 0
    ret: list[tuple[int, int]] = []
    for _, a, b, _ in vec:
        x += a
        y += b
        ret.append((x, y))
    return ret


def solve() -> bool:
    n = int(input())

    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))

    AB = [(Fraction(b, a), a, b, i) for i, (a, b) in enumerate(zip(A, B))]
    CD = [(Fraction(d, c), c, d, i) for i, (c, d) in enumerate(zip(C, D))]

    AB.sort()
    CD.sort()

    lb_xys = to_slope(AB)  # 初期状態の y = f(x) の折れ線
    ub_xys = to_slope(CD)  # 所望の最終状態の y = f(x) の折れ線

    # 最終状態の折れ線が初期状態の折れ線の下側を通っていたら明らかに No
    for (x0, y0), (x1, y1) in zip([(0, 0)] + lb_xys[:-1], lb_xys, strict=True):
        for x, y in ub_xys:
            if (x1 - x0) * (y - y0) - (y1 - y0) * (x - x0) < 0:
                return False

    # 初期状態と最終状態で濃度の大小関係が一致していたら Yes
    if [i for _, _, _, i in AB] == [i for _, _, _, i in CD]:
        return True

    # n - 1 本以下の線分で (0, 0) から右上まで到達できたら Yes
    vx, vy = Fraction(0, 1), Fraction(0, 1)  # 現在位置
    for i in range(n - 1):
        # (vx, vy) から出て (px, py) を通る直線を考える
        px, py = ub_xys[i]

        if px <= vx:
            return True

        # y = a1 x + b1
        a1 = (py - vy) / (px - vx)
        b1 = vy - a1 * vx

        # y = a2 x + b2
        ax, ay = lb_xys[i]
        bx, by = lb_xys[i + 1]

        a2 = Fraction(by - ay, bx - ax)
        b2 = ay - a2 * ax

        if a1 >= a2:
            return True

        vx = (b2 - b1) / (a1 - a2)
        vy = a1 * vx + b1

        if vx >= bx:
            return True

    return False


print("Yes" if solve() else "No")

yukicoder

結果

テストケース

ソースコード