結果
問題 | No.2254 Reverse Only |
ユーザー |
![]() |
提出日時 | 2023-03-10 01:39:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 319 ms / 2,000 ms |
コード長 | 1,812 bytes |
コンパイル時間 | 310 ms |
コンパイル使用メモリ | 82,720 KB |
実行使用メモリ | 126,888 KB |
最終ジャッジ日時 | 2024-09-18 03:11:20 |
合計ジャッジ時間 | 8,931 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
import random def isprime(n): if n == 1: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True def RandomMod(l,r): ret = random.randrange(l, r) while not isprime(ret): ret = random.randrange(l, r) return ret mod1 = RandomMod(7*10**8, 10**9) b1 = random.randrange(200000, 300000) mod2 = RandomMod(7*10**8, 10**9) b2 = random.randrange(200000, 300000) n,k = map(int,input().split()) a = list(map(int,input().split())) b = list(map(int,input().split())) b1l = [0] * (n+1) b1l[0] = 1 for i in range(n): b1l[i+1] = b1l[i] * b1 % mod1 b2l = [0] * (n+1) b2l[0] = 1 for i in range(n): b2l[i+1] = b2l[i] * b2 % mod2 if a == b: print("Yes") exit() if sorted(a) != sorted(b): print("No") exit() if k > n: print("No") elif k <= n - 2: print("Yes") elif k == n: if a[::-1] == b: print("Yes") else: print("No") else: # k = n-1 s1 = [0] * (n + 1) s2 = [0] * (n + 1) x1 = 0 x2 = 0 q1 = 0 q2 = 0 for i in range(n): x1 = (x1 * b1 + a[i]) % mod1 x2 = (x2 * b2 + a[i]) % mod2 q1 = (q1 * b1 + b[i]) % mod1 q2 = (q2 * b2 + b[i]) % mod2 s1[i+1] = x1 s2[i+1] = x2 t1 = [0] * (n + 1) t2 = [0] * (n + 1) x1 = 0 x2 = 0 for i in range(n): x1 = (x1 * b1 + a[n-1-i]) % mod1 x2 = (x2 * b2 + a[n-1-i]) % mod2 t1[i+1] = x1 t2[i+1] = x2 # a[:i] + a[i:] # s[i] + (s[n] - s[i] * b1l[n-i]) * b1l[i] for i in range(n + 1): y1 = (s1[i] + (s1[n] - s1[i] * b1l[n-i]) * b1l[i]) % mod1 y2 = (s2[i] + (s2[n] - s2[i] * b2l[n-i]) * b2l[i]) % mod2 #print(y1,y2,q1,q2) if y1 == q1 and y2 == q2: print("Yes") exit() for i in range(n + 1): y1 = (t1[i] + (t1[n] - t1[i] * b1l[n-i]) * b1l[i]) % mod1 y2 = (t2[i] + (t2[n] - t2[i] * b2l[n-i]) * b2l[i]) % mod2 if y1 == q1 and y2 == q2: print("Yes") exit() print("No")