結果
問題 | No.1544 [Cherry 2nd Tune C] Synchroscope |
ユーザー | sangonana |
提出日時 | 2021-06-11 21:40:06 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 519 ms / 2,000 ms |
コード長 | 819 bytes |
コンパイル時間 | 512 ms |
コンパイル使用メモリ | 87,032 KB |
実行使用メモリ | 77,204 KB |
最終ジャッジ日時 | 2023-08-21 11:52:46 |
合計ジャッジ時間 | 8,932 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,392 KB |
testcase_01 | AC | 73 ms
71,112 KB |
testcase_02 | AC | 71 ms
71,544 KB |
testcase_03 | AC | 112 ms
77,012 KB |
testcase_04 | AC | 143 ms
76,752 KB |
testcase_05 | AC | 120 ms
77,192 KB |
testcase_06 | AC | 127 ms
77,084 KB |
testcase_07 | AC | 128 ms
76,980 KB |
testcase_08 | AC | 116 ms
76,992 KB |
testcase_09 | AC | 83 ms
76,332 KB |
testcase_10 | AC | 128 ms
76,980 KB |
testcase_11 | AC | 111 ms
76,596 KB |
testcase_12 | AC | 117 ms
77,036 KB |
testcase_13 | AC | 84 ms
76,812 KB |
testcase_14 | AC | 143 ms
77,204 KB |
testcase_15 | AC | 152 ms
76,988 KB |
testcase_16 | AC | 108 ms
77,128 KB |
testcase_17 | AC | 102 ms
76,792 KB |
testcase_18 | AC | 83 ms
76,836 KB |
testcase_19 | AC | 86 ms
76,536 KB |
testcase_20 | AC | 142 ms
76,928 KB |
testcase_21 | AC | 98 ms
76,740 KB |
testcase_22 | AC | 85 ms
76,704 KB |
testcase_23 | AC | 173 ms
77,024 KB |
testcase_24 | AC | 173 ms
76,684 KB |
testcase_25 | AC | 174 ms
77,188 KB |
testcase_26 | AC | 174 ms
77,020 KB |
testcase_27 | AC | 174 ms
76,736 KB |
testcase_28 | AC | 175 ms
77,084 KB |
testcase_29 | AC | 174 ms
77,100 KB |
testcase_30 | AC | 172 ms
76,940 KB |
testcase_31 | AC | 174 ms
77,088 KB |
testcase_32 | AC | 177 ms
76,672 KB |
testcase_33 | AC | 519 ms
76,916 KB |
testcase_34 | AC | 72 ms
71,300 KB |
testcase_35 | AC | 73 ms
71,296 KB |
testcase_36 | AC | 79 ms
76,408 KB |
testcase_37 | AC | 78 ms
76,140 KB |
testcase_38 | AC | 164 ms
76,496 KB |
testcase_39 | AC | 164 ms
76,448 KB |
testcase_40 | AC | 164 ms
76,448 KB |
testcase_41 | AC | 164 ms
76,728 KB |
testcase_42 | AC | 164 ms
76,516 KB |
testcase_43 | AC | 163 ms
76,464 KB |
testcase_44 | AC | 162 ms
76,536 KB |
testcase_45 | AC | 166 ms
76,820 KB |
testcase_46 | AC | 162 ms
76,612 KB |
testcase_47 | AC | 164 ms
76,764 KB |
ソースコード
from math import gcd def crt(R,M): def ex_gcd(a,b,c): GCD=gcd(a,b) if GCD>1: if c%GCD!=0: return -1 else: a//=GCD b//=GCD c//=GCD x1,y1,m=1,0,a x2,y2,n=0,1,b while m%n!=0: q=m//n x1,y1,m,x2,y2,n=\ x2,y2,n,x1-q*x2,y1-q*y2,m-q*n return (x2*c,y2*c) N=len(M) for i in range(N-1): D=gcd(M[i],M[i+1]) if (R[i+1]-R[i])%D!=0: return None P,Q=ex_gcd(M[i],M[i+1],D) ret=R[i]+M[i]*((R[i+1]-R[i])//D)*P ret%=M[i]*M[i+1]//D if i!=N-2: R[i+1]=ret M[i+1]=M[i]*M[i+1]//D return ret n,m=map(int,input().split()) a=list(map(int,input().split())) b=list(map(int,input().split())) inf=10**18 ans=inf for i in range(n): for j in range(m): if a[i]==b[j]: try: ret=crt([i,j],[n,m]) ans=min(ans,ret+1) except: continue if ans==inf: ans=-1 print(ans)