結果
| 問題 | No.2254 Reverse Only |
| ユーザー |
 yupooh
|
| 提出日時 | 2023-03-24 22:48:32 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 268 ms / 2,000 ms |
| コード長 | 7,445 bytes |
| コンパイル時間 | 265 ms |
| コンパイル使用メモリ | 81,740 KB |
| 実行使用メモリ | 148,924 KB |
| 最終ジャッジ日時 | 2024-09-18 17:25:02 |
| 合計ジャッジ時間 | 9,375 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 49 ms
55,552 KB |
| testcase_01 | AC | 45 ms
55,296 KB |
| testcase_02 | AC | 46 ms
55,296 KB |
| testcase_03 | AC | 45 ms
55,040 KB |
| testcase_04 | AC | 46 ms
54,912 KB |
| testcase_05 | AC | 44 ms
55,296 KB |
| testcase_06 | AC | 44 ms
55,000 KB |
| testcase_07 | AC | 49 ms
55,040 KB |
| testcase_08 | AC | 243 ms
148,368 KB |
| testcase_09 | AC | 268 ms
148,208 KB |
| testcase_10 | AC | 150 ms
126,984 KB |
| testcase_11 | AC | 239 ms
148,896 KB |
| testcase_12 | AC | 246 ms
148,480 KB |
| testcase_13 | AC | 234 ms
148,452 KB |
| testcase_14 | AC | 238 ms
148,924 KB |
| testcase_15 | AC | 240 ms
148,376 KB |
| testcase_16 | AC | 251 ms
147,236 KB |
| testcase_17 | AC | 260 ms
148,884 KB |
| testcase_18 | AC | 254 ms
148,852 KB |
| testcase_19 | AC | 149 ms
126,828 KB |
| testcase_20 | AC | 194 ms
147,980 KB |
| testcase_21 | AC | 199 ms
147,724 KB |
| testcase_22 | AC | 218 ms
132,160 KB |
| testcase_23 | AC | 238 ms
130,624 KB |
| testcase_24 | AC | 186 ms
128,400 KB |
| testcase_25 | AC | 197 ms
127,356 KB |
| testcase_26 | AC | 197 ms
127,104 KB |
| testcase_27 | AC | 60 ms
68,336 KB |
| testcase_28 | AC | 97 ms
90,012 KB |
| testcase_29 | AC | 143 ms
110,812 KB |
| testcase_30 | AC | 135 ms
105,092 KB |
| testcase_31 | AC | 100 ms
92,464 KB |
| testcase_32 | AC | 103 ms
92,840 KB |
| testcase_33 | AC | 83 ms
84,808 KB |
| testcase_34 | AC | 164 ms
120,076 KB |
| testcase_35 | AC | 124 ms
95,620 KB |
| testcase_36 | AC | 210 ms
137,036 KB |
| testcase_37 | AC | 218 ms
140,208 KB |
| testcase_38 | AC | 88 ms
88,192 KB |
| testcase_39 | AC | 194 ms
132,704 KB |
| testcase_40 | AC | 57 ms
68,224 KB |
| testcase_41 | AC | 117 ms
95,380 KB |
| testcase_42 | AC | 90 ms
88,192 KB |
| testcase_43 | AC | 170 ms
123,032 KB |
| testcase_44 | AC | 226 ms
144,452 KB |
| testcase_45 | AC | 164 ms
117,912 KB |
| testcase_46 | AC | 57 ms
67,328 KB |
ソースコード
import sys
input = sys.stdin.readline
from collections import defaultdict
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
def _sa_naive(s):
n = len(s)
sa = list(range(0, n))
sa.sort(key=lambda i: s[i:])
return sa
def _sa_doubling(s):
n = len(s)
sa = list(range(n))
sa_mapped = []
rnk = s.copy()
tmp = [0] * n
k = 1
while k < n:
sa_mapped.clear()
for t in sa:
sa_mapped.append(
((rnk[t] << 32) + (rnk[t + k] if t + k < n else -1), t))
sa_mapped.sort(key=lambda t: t[0])
sa.clear()
for t in sa_mapped:
sa.append(t[1])
tmp[sa[0]] = 0
for i in range(1, n):
x = sa[i - 1]
y = sa[i]
if rnk[x] != rnk[y]:
alpha = 1 if rnk[x] < rnk[y] else 0
else:
rx = rnk[x + k] if x + k < n else -1
ry = rnk[y + k] if y + k < n else -1
alpha = 1 if rx < ry else 0
tmp[sa[i]] = tmp[sa[i - 1]] + alpha
tmp, rnk = rnk, tmp
k *= 2
return sa
def _sa_is(s, upper):
n = len(s)
if n == 0:
return []
if n == 1:
return [0]
if n == 2:
if s[0] < s[1]:
return [0, 1]
else:
return [1, 0]
sa = [-1] * n
ls = [False] * n
for i in range(n - 1)[::-1]:
if s[i] == s[i + 1]:
ls[i] = ls[i + 1]
else:
ls[i] = (s[i] < s[i + 1])
sum_l = [0] * (upper + 1)
sum_s = [0] * (upper + 1)
for i in range(n):
if not ls[i]:
sum_s[s[i]] += 1
else:
sum_l[s[i] + 1] += 1
for i in range(upper + 1):
sum_s[i] += sum_l[i]
if i < upper:
sum_l[i + 1] += sum_s[i]
def induce(lms):
nonlocal sa
sa = [-1] * n
buf = sum_s.copy()
for d in lms:
if d == n:
continue
sa[buf[s[d]]] = d
buf[s[d]] += 1
buf = sum_l.copy()
sa[buf[s[n - 1]]] = n - 1
buf[s[n - 1]] += 1
for i in range(n):
v = sa[i]
if v >= 1 and not ls[v - 1]:
sa[buf[s[v - 1]]] = v - 1
buf[s[v - 1]] += 1
buf = sum_l.copy()
for i in range(n)[::-1]:
v = sa[i]
if v >= 1 and ls[v - 1]:
buf[s[v - 1] + 1] -= 1
sa[buf[s[v - 1] + 1]] = v - 1
lms_map = [-1] * (n + 1)
m = 0
for i in range(1, n):
if (not ls[i - 1]) and ls[i]:
lms_map[i] = m
m += 1
lms = []
for i in range(1, n):
if (not ls[i - 1]) and ls[i]:
lms.append(i)
induce(lms)
if m:
sorted_lms = []
for v in sa:
if lms_map[v] != -1:
sorted_lms.append(v)
rec_s = [0] * m
rec_upper = 0
rec_s[lms_map[sorted_lms[0]]] = 0
for i in range(1, m):
l = sorted_lms[i - 1]
r = sorted_lms[i]
if lms_map[l] + 1 < m:
end_l = lms[lms_map[l] + 1]
else:
end_l = n
if lms_map[r] + 1 < m:
end_r = lms[lms_map[r] + 1]
else:
end_r = n
same = True
if end_l - l != end_r - r:
same = False
else:
while l < end_l:
if s[l] != s[r]:
break
l += 1
r += 1
if l == n or s[l] != s[r]:
same = False
if not same:
rec_upper += 1
rec_s[lms_map[sorted_lms[i]]] = rec_upper
rec_sa = _sa_is(rec_s, rec_upper)
for i in range(m):
sorted_lms[i] = lms[rec_sa[i]]
induce(sorted_lms)
return sa
def suffix_array(s, upper=None):
"""Given a string (or a list of integers) `s` of length n, it returns the suffix array of `s`.
Here, the suffix array `sa` of `s` is a permutation of 0, ..., n-1
such that `s[sa[i]:n] < s[sa[i+1]:n]` holds for all i = 0, 1, ..., n-2.
Constraints
-----------
> 0 <= n <= 10 ** 8
> 0 <= upper <= 10 ** 8
> The type of `s` is either a string or a list of integers. Otherwise, it raises `TypeError`.
> 0 <= x <= upper for all elements x of `s` if `s` is a list of integers and upper is given.
Complexity
----------
> O(n)-time if `s` is a string and upper is not given.
> O(n log n)-time and O(n)-space if `s` is a list of integers and upper is not given.
> O(n + upper)-time if upper is given.
"""
if upper is None:
if isinstance(s, str):
s = [ord(c) for c in s]
return _sa_is(s, 255)
elif isinstance(s, list):
etoi = {e: i for i, e in enumerate(sorted(set(s)))}
return _sa_is([etoi[e] for e in s], len(etoi))
else:
raise TypeError(
f"The argument 's' must be a string or a list of integers, not {type(s).__name__}")
else:
assert 0 <= upper
assert all(0 <= d <= upper for d in s)
return _sa_is(s, upper)
def lcp_array(s, sa):
"""Given a string (or a list of integers) `s` of length n, it returns the LCP array of `s`.
Here, the LCP array of `s` is the array of length n-1,
such that the i-th element is the length of the LCP (Longest Common Prefix) of `s[sa[i]:n]` and `s[sa[i+1]:n]`.
Constraints
-----------
> `sa` is the suffix array of `s`.
> 1 <= n <= 10 ** 8
Complexity
----------
> O(n)
"""
n = len(s)
assert n >= 1
rnk = [0] * n
for i in range(n):
rnk[sa[i]] = i
lcp = [0] * (n - 1)
h = 0
for i in range(n):
if h > 0:
h -= 1
if rnk[i] == 0:
continue
j = sa[rnk[i] - 1]
while j + h < n and i + h < n:
if s[j + h] != s[i + h]:
break
h += 1
lcp[rnk[i] - 1] = h
return lcp
def z_algorithm(s):
"""Given a string (or a list of integers) of length n, it returns the array of length n,
such that the i-th element is the length of the LCP (Longest Common Prefix) of `s[0:n]` and `s[i:n]`.
Constraints
-----------
> 0 <= n <= 10 ** 8
Complexity
----------
> O(n)
"""
n = len(s)
if n == 0:
return []
z = [0] * n
i = 1
j = 0
while i < n:
z[i] = 0 if (j + z[j] <= i) else min(j + z[j] - i, z[i - j])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if j + z[j] < i + z[i]:
j = i
i += 1
z[0] = n
return z
dica=defaultdict(int)
dicb=defaultdict(int)
for i in a:
dica[i]+=1
for i in b:
dicb[i]+=1
flg=True
for i in dica:
if dica[i]!=dicb[i]:
flg=False
if not flg:
print("No")
exit()
if k<=n-2:
print("Yes")
exit()
if a==b:
print("Yes")
exit()
if k>n:
print("No")
exit()
if k==n:
if a==b[::-1]:
print("Yes")
else:
print("No")
exit()
l=a+[0]+b+b
lz=z_algorithm(l)
for i in range(n+1,len(lz)):
if lz[i]>=n:
print("Yes")
exit()
l=a[::-1]+[0]+b+b
lz=z_algorithm(l)
for i in range(n+1,len(lz)):
if lz[i]>=n:
print("Yes")
exit()
print("No")