結果
問題 | No.2594 Mix shake!! |
ユーザー | 👑 Nachia |
提出日時 | 2023-12-22 06:17:12 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,910 bytes |
コンパイル時間 | 119 ms |
コンパイル使用メモリ | 12,288 KB |
実行使用メモリ | 19,732 KB |
最終ジャッジ日時 | 2023-12-22 06:17:19 |
合計ジャッジ時間 | 6,432 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 32 ms
17,300 KB |
testcase_01 | AC | 33 ms
10,496 KB |
testcase_02 | AC | 31 ms
10,496 KB |
testcase_03 | AC | 31 ms
10,496 KB |
testcase_04 | AC | 32 ms
10,496 KB |
testcase_05 | AC | 31 ms
10,496 KB |
testcase_06 | AC | 32 ms
10,496 KB |
testcase_07 | AC | 32 ms
10,496 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 32 ms
10,496 KB |
testcase_12 | AC | 32 ms
10,496 KB |
testcase_13 | WA | - |
testcase_14 | AC | 32 ms
10,496 KB |
testcase_15 | AC | 32 ms
10,496 KB |
testcase_16 | AC | 32 ms
10,496 KB |
testcase_17 | AC | 32 ms
10,496 KB |
testcase_18 | AC | 34 ms
10,496 KB |
testcase_19 | AC | 33 ms
10,496 KB |
testcase_20 | AC | 41 ms
10,496 KB |
testcase_21 | AC | 32 ms
10,496 KB |
testcase_22 | AC | 41 ms
10,496 KB |
testcase_23 | AC | 796 ms
10,880 KB |
testcase_24 | AC | 42 ms
10,496 KB |
testcase_25 | AC | 31 ms
10,496 KB |
testcase_26 | WA | - |
testcase_27 | AC | 31 ms
10,496 KB |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | TLE | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
testcase_50 | -- | - |
testcase_51 | -- | - |
testcase_52 | -- | - |
testcase_53 | -- | - |
testcase_54 | -- | - |
testcase_55 | -- | - |
testcase_56 | -- | - |
testcase_57 | -- | - |
testcase_58 | -- | - |
testcase_59 | -- | - |
testcase_60 | -- | - |
testcase_61 | -- | - |
testcase_62 | -- | - |
testcase_63 | -- | - |
testcase_64 | -- | - |
testcase_65 | -- | - |
testcase_66 | -- | - |
testcase_67 | -- | - |
testcase_68 | -- | - |
testcase_69 | -- | - |
testcase_70 | -- | - |
testcase_71 | -- | - |
testcase_72 | -- | - |
testcase_73 | -- | - |
testcase_74 | -- | - |
testcase_75 | -- | - |
testcase_76 | -- | - |
testcase_77 | -- | - |
testcase_78 | -- | - |
testcase_79 | -- | - |
testcase_80 | -- | - |
testcase_81 | -- | - |
testcase_82 | -- | - |
testcase_83 | -- | - |
testcase_84 | -- | - |
testcase_85 | -- | - |
testcase_86 | -- | - |
testcase_87 | -- | - |
ソースコード
import math def cmp_fracs(a, b) : return a[0] * b[1] < a[1] * b[0] def add_frac(a, b) : return [ a[0] * b[1] + a[1] * b[0], a[1] * b[1] ] def sub_frac(a, b) : return [ a[0] * b[1] - a[1] * b[0], a[1] * b[1] ] def mul_frac(a, b) : return [ a[0] * b[0], a[1] * b[1] ] def div_frac(a, b) : return [ a[0] * b[1], a[1] * b[0] ] def refine_frac(a) : g = math.gcd(a[0], a[1]) return [ a[0] // g, a[1] // g ] ZERO_FRAC = [0,1] def verify2(a : list[list[int]], b : list[list[int]], max_t : int) : a2 = [[ZERO_FRAC,ZERO_FRAC]] for x in a : a2.append([ add_frac(a2[-1][0], [x[0],1]), add_frac(a2[-1][1], [x[1],1]) ]) b2 = [[ZERO_FRAC,ZERO_FRAC]] for x in b : b2.append([ add_frac(b2[-1][0], [x[0],1]), add_frac(b2[-1][1], [x[1],1]) ]) px = ZERO_FRAC py = ZERO_FRAC t = 0 while cmp_fracs(px, b2[-1][0]) : t += 1 if t > max_t : return False min_slope = [1,0] for bp in b2 : if not cmp_fracs(px, bp[0]) : continue dx = sub_frac(bp[0], px) dy = sub_frac(bp[1], py) slope = div_frac(dy, dx) if cmp_fracs(slope, min_slope) : min_slope = slope found = 0 for ap0,ap1 in zip(a2[:-1],a2[1:]) : if not cmp_fracs(px, ap1[0]) : continue a1xf = sub_frac(ap1[0], px) a1yf = sub_frac(ap1[1], py) slope = div_frac(a1yf, a1xf) if not cmp_fracs(min_slope, slope) : continue a1yf = sub_frac(a1yf, mul_frac(a1xf, min_slope)) dxa = sub_frac(ap1[0],ap0[0]) dya = sub_frac(ap1[1],ap0[1]) aslope = sub_frac(div_frac(dya, dxa), min_slope) crossx = sub_frac(ap1[0], div_frac(a1yf, aslope)) crossy = add_frac(py, mul_frac(slope, sub_frac(crossx, px))) px = refine_frac(crossx) py = refine_frac(crossy) found = 1 break if found == 0 : break return True def input_positions(n) : ax = list(map(int,input().split())) ay = list(map(int,input().split())) return [ [ax[i],ay[i]] for i in range(n) ] def get_arg_order(a : list[list[int]]) : a = [[x[0],x[1]] for x in a] res = [i for i in range(len(a))] for i in range(n) : for j in range(n-1) : if a[j][0] * a[j+1][1] < a[j][1] * a[j+1][0] : res[j], res[j+1] = res[j+1], res[j] a[j], a[j+1] = a[j+1], a[j] return res n = int(input()) a = input_positions(n) b = input_positions(n) a_ord = get_arg_order(a) b_ord = get_arg_order(b) a_sorted = [a[i] for i in a_ord] b_sorted = [b[i] for i in b_ord] a_model = [a[i] for i in b_ord] b_model = [b[i] for i in b_ord] if verify2(a_model, b_model, n) : print("Yes") exit() if verify2(a_sorted, b_sorted, n-1) : print("Yes") exit() print("No")