結果
| 問題 |
No.2254 Reverse Only
|
| コンテスト | |
| ユーザー |
 yupooh
|
| 提出日時 | 2023-03-24 22:43:11 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,447 bytes |
| コンパイル時間 | 350 ms |
| コンパイル使用メモリ | 82,128 KB |
| 実行使用メモリ | 149,632 KB |
| 最終ジャッジ日時 | 2024-09-18 17:23:24 |
| 合計ジャッジ時間 | 8,604 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 44 WA * 3 |
ソースコード
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")