結果
問題 | No.2594 Mix shake!! |
ユーザー | 👑 Nachia |
提出日時 | 2023-12-22 06:31:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 2,957 bytes |
コンパイル時間 | 231 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 76,012 KB |
最終ジャッジ日時 | 2023-12-22 06:31:58 |
合計ジャッジ時間 | 8,765 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
53,588 KB |
testcase_01 | AC | 38 ms
53,588 KB |
testcase_02 | AC | 37 ms
53,588 KB |
testcase_03 | AC | 36 ms
53,588 KB |
testcase_04 | AC | 37 ms
53,588 KB |
testcase_05 | AC | 36 ms
53,588 KB |
testcase_06 | AC | 36 ms
53,588 KB |
testcase_07 | AC | 36 ms
53,588 KB |
testcase_08 | AC | 37 ms
53,588 KB |
testcase_09 | AC | 36 ms
53,588 KB |
testcase_10 | AC | 38 ms
53,588 KB |
testcase_11 | AC | 37 ms
53,588 KB |
testcase_12 | AC | 47 ms
53,588 KB |
testcase_13 | AC | 38 ms
53,588 KB |
testcase_14 | AC | 38 ms
53,588 KB |
testcase_15 | AC | 37 ms
53,588 KB |
testcase_16 | AC | 37 ms
53,588 KB |
testcase_17 | AC | 37 ms
53,588 KB |
testcase_18 | AC | 43 ms
61,592 KB |
testcase_19 | AC | 44 ms
61,604 KB |
testcase_20 | AC | 65 ms
73,044 KB |
testcase_21 | AC | 37 ms
53,588 KB |
testcase_22 | AC | 59 ms
72,388 KB |
testcase_23 | AC | 61 ms
72,388 KB |
testcase_24 | AC | 37 ms
53,588 KB |
testcase_25 | AC | 36 ms
53,588 KB |
testcase_26 | AC | 36 ms
53,588 KB |
testcase_27 | AC | 36 ms
53,588 KB |
testcase_28 | AC | 36 ms
53,588 KB |
testcase_29 | AC | 37 ms
53,588 KB |
testcase_30 | AC | 36 ms
53,588 KB |
testcase_31 | AC | 38 ms
53,588 KB |
testcase_32 | AC | 78 ms
75,576 KB |
testcase_33 | AC | 76 ms
75,576 KB |
testcase_34 | AC | 157 ms
75,832 KB |
testcase_35 | AC | 158 ms
75,832 KB |
testcase_36 | AC | 160 ms
75,960 KB |
testcase_37 | AC | 158 ms
76,008 KB |
testcase_38 | AC | 161 ms
75,884 KB |
testcase_39 | AC | 157 ms
75,836 KB |
testcase_40 | AC | 170 ms
75,704 KB |
testcase_41 | AC | 156 ms
75,700 KB |
testcase_42 | AC | 162 ms
75,836 KB |
testcase_43 | AC | 160 ms
75,960 KB |
testcase_44 | AC | 163 ms
75,832 KB |
testcase_45 | AC | 157 ms
75,960 KB |
testcase_46 | AC | 160 ms
75,836 KB |
testcase_47 | AC | 169 ms
76,012 KB |
testcase_48 | AC | 164 ms
75,836 KB |
testcase_49 | AC | 161 ms
75,880 KB |
testcase_50 | AC | 160 ms
75,836 KB |
testcase_51 | AC | 166 ms
75,960 KB |
testcase_52 | AC | 159 ms
75,704 KB |
testcase_53 | AC | 158 ms
75,704 KB |
testcase_54 | AC | 45 ms
61,592 KB |
testcase_55 | AC | 42 ms
61,592 KB |
testcase_56 | AC | 36 ms
53,588 KB |
testcase_57 | AC | 37 ms
53,588 KB |
testcase_58 | AC | 36 ms
53,588 KB |
testcase_59 | AC | 36 ms
53,588 KB |
testcase_60 | AC | 38 ms
53,588 KB |
testcase_61 | AC | 36 ms
53,588 KB |
testcase_62 | AC | 38 ms
53,588 KB |
testcase_63 | AC | 37 ms
53,588 KB |
testcase_64 | AC | 37 ms
53,588 KB |
testcase_65 | AC | 37 ms
53,588 KB |
testcase_66 | AC | 57 ms
70,444 KB |
testcase_67 | AC | 58 ms
70,444 KB |
testcase_68 | AC | 63 ms
72,520 KB |
testcase_69 | AC | 58 ms
70,448 KB |
testcase_70 | AC | 58 ms
70,448 KB |
testcase_71 | AC | 60 ms
70,448 KB |
testcase_72 | AC | 37 ms
53,588 KB |
testcase_73 | AC | 37 ms
53,588 KB |
testcase_74 | AC | 39 ms
53,588 KB |
testcase_75 | AC | 38 ms
53,588 KB |
testcase_76 | AC | 37 ms
53,588 KB |
testcase_77 | AC | 36 ms
53,588 KB |
testcase_78 | AC | 36 ms
53,588 KB |
testcase_79 | AC | 36 ms
53,588 KB |
testcase_80 | AC | 44 ms
61,720 KB |
testcase_81 | AC | 58 ms
70,444 KB |
testcase_82 | AC | 56 ms
70,444 KB |
testcase_83 | AC | 58 ms
70,444 KB |
testcase_84 | AC | 75 ms
75,840 KB |
testcase_85 | AC | 58 ms
70,448 KB |
testcase_86 | AC | 58 ms
70,448 KB |
testcase_87 | AC | 58 ms
70,444 KB |
ソースコード
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 min_slope = refine_frac(min_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(min_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")