Submission #75816997

---

Source Code Expand

n,m = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
pi = [0]*m
j = 0
for i in range(1,m):
    while j > 0 and B[i] != B[j]:
        j = pi[j-1]
    if B[i] == B[j]:
        j += 1
        pi[i] = j
over = pi[m-1]

a,b,c = {},{},{}
for i in A:
    if i in a: a[i] += 1
    else: a[i] = 1
for i in B:
    if i in b: b[i] += 1
    else: b[i] = 1

C = B[over:]
for i in C:
    if i in c: c[i] += 1
    else: c[i] = 1

f = True
for i in b:
    if i not in a or a[i] < b[i]:
        f = False
        break
if not f:
    print(*A)
    exit()
for i in b:
    a[i] -= b[i]

x = float('inf')
for i in c:
    if i not in a:
        x = 0
        break
    x = min(x,a[i]//c[i])
if x:
    for i in c:
        a[i] -= c[i]*x

l = n-m-(m-over)*x
L = [0]*l+B+C*x
idx = 0
for i in a:
    c = a[i]
    for j in range(idx,idx+c):
        L[j] = i
    idx += c
print(*L)

Submission Info

Judge Result