結果

問題 No.2594 Mix shake!!
ユーザー SumitacchanSumitacchan
提出日時 2023-12-10 18:19:51
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 2,324 bytes
コンパイル時間 80 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2023-12-20 01:04:59
合計ジャッジ時間 5,570 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
11,392 KB
testcase_01 RE -
testcase_02 AC 37 ms
11,392 KB
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 AC 38 ms
11,392 KB
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 AC 38 ms
11,392 KB
testcase_18 AC 38 ms
11,520 KB
testcase_19 RE -
testcase_20 AC 38 ms
11,520 KB
testcase_21 RE -
testcase_22 AC 37 ms
11,520 KB
testcase_23 AC 38 ms
11,520 KB
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 AC 38 ms
11,520 KB
testcase_55 AC 38 ms
11,520 KB
testcase_56 AC 37 ms
11,392 KB
testcase_57 AC 37 ms
11,392 KB
testcase_58 AC 37 ms
11,392 KB
testcase_59 AC 37 ms
11,392 KB
testcase_60 AC 37 ms
11,392 KB
testcase_61 AC 38 ms
11,392 KB
testcase_62 AC 37 ms
11,392 KB
testcase_63 AC 38 ms
11,392 KB
testcase_64 AC 37 ms
11,392 KB
testcase_65 AC 38 ms
11,392 KB
testcase_66 RE -
testcase_67 AC 38 ms
11,520 KB
testcase_68 RE -
testcase_69 AC 38 ms
11,520 KB
testcase_70 RE -
testcase_71 AC 39 ms
11,520 KB
testcase_72 AC 37 ms
11,392 KB
testcase_73 AC 38 ms
11,392 KB
testcase_74 AC 37 ms
11,392 KB
testcase_75 AC 37 ms
11,392 KB
testcase_76 AC 36 ms
11,392 KB
testcase_77 AC 37 ms
11,392 KB
testcase_78 AC 37 ms
11,392 KB
testcase_79 AC 37 ms
11,392 KB
testcase_80 RE -
testcase_81 AC 39 ms
11,520 KB
testcase_82 RE -
testcase_83 AC 37 ms
11,520 KB
testcase_84 AC 39 ms
11,520 KB
testcase_85 AC 38 ms
11,520 KB
testcase_86 AC 51 ms
11,520 KB
testcase_87 AC 39 ms
11,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# -*- coding: utf-8 -*-
from fractions import Fraction
import sys
from typing import Sequence

def validate(n: int, a: Sequence[int], b: Sequence[int], c: Sequence[int], d: Sequence[int]) -> None:
    MIN_N = 2
    MAX_N = 50
    MIN_VAL = 1
    MAX_VAL = 10 ** 17
    
    assert MIN_N <= n <= MAX_N
    for seq in [a, b, c, d]:
        assert len(seq) == n
        assert all(MIN_VAL <= x <= MAX_VAL for x in seq)
    
    assert sum(a) == sum(c)
    assert sum(b) == sum(d)

def output_ans(ans: bool) -> None:
    if ans:
        print("Yes")
    else:
        print("No")
    sys.exit()

def compute_slope(n: int, a: Sequence[int], b: Sequence[int]) -> tuple[list[tuple[int, int]], list[int]]:
    """b[i]/a[i] の昇順に加算した (aの累積和,bの累積和) と、昇順のソートした際の index の列を返す"""
    p: list[int] = sorted(list(range(n)), key=lambda i: Fraction(b[i], a[i]))
    slope: list[tuple[int, int]] = [(0, 0)]
    for i in p:
        x, y = slope[-1]
        slope.append((x + a[i], y + b[i]))
    return slope, p

def evaluate(slope: Sequence[int], x: int) -> Fraction:
    for i in range(len(slope) - 1):
        if slope[i][0] <= x <= slope[i + 1][0]:
            x0, y0 = slope[i]
            x1, y1 = slope[i + 1]
            return Fraction((x1 - x) * y0 + (x - x0) * y1, x1 - x0)
    assert False


if __name__ == "__main__":
    n: int = int(input())
    a: list[int] = list(map(int, input().split()))
    b: list[int] = list(map(int, input().split()))
    c: list[int] = list(map(int, input().split()))
    d: list[int] = list(map(int, input().split()))
    validate(n, a, b, c, d)
    
    ls, lp = compute_slope(n, a, b)
    us, up = compute_slope(n, c, d)
    assert ls[0] == us[0] == (0, 0)
    assert len(ls) == len(us) == n + 1 and ls[n] == us[n]

    # us が ls の上側にない場合は不可
    for x, y in us[1: n]:
        if y < evaluate(ls, x):
            output_ans(False)
    for x, y in ls[1: n]:
        if y > evaluate(us, x):
            output_ans(False)
    # 以下、us は ls の上側にあることが保証されている

    # 濃度の順番が同じならば可能
    if lp == up:
        output_ans(True)
    
    # 2つの容器で濃度が同一であるような中間状態が必要
    raise NotImplementedError # これから
0