Submission #75821883

Source Code Expand

#C
N, M = map(int, input().split())
from collections import defaultdict
a = list(map(int, input().split()))
b = list(map(int, input().split()))
counter = defaultdict(int)

for i in a:
    counter[i] += 1

fail = [0]*M
j = 0
for i in range(1, M):
    while j >0 and b[i] != b[j]:
        j = fail[j - 1]
    if b[i] == b[j]:
        j += 1
        fail[i] = j


c = b[M-fail[-1]:]
b = b[:M-fail[-1]]
c = c[-(len(c)%len(b)):]

counter2 = defaultdict(int)
for i in b:
    counter2[i] += 1
counter3 = defaultdict(int)
for i in c:
    counter3[i] += 1

ans = 9999999999999
for i in counter2:
    ans = min(ans, counter[i]//counter2[i])

for i in counter2:
    counter[i] -= ans*counter2[i]

tmp = b*ans

for i in counter3:
    if counter[i] < counter3[i]:
        break
else:
    tmp += c
    for i in counter3:
        counter[i] -= counter3[i]

for i in counter:
    tmp += [i]*counter[i]
print(*tmp)

Submission Info

Submission Time
Task C - Rearrangement
User kkigon
Language Python (PyPy 3.11-v7.3.20)
Score 100
Code Size 949 Byte
Status AC
Exec Time 1377 ms
Memory 413884 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 50
Set Name Test Cases
Sample 00-sample-001.txt, 00-sample-002.txt
All 00-sample-001.txt, 00-sample-002.txt, 01-003.txt, 01-004.txt, 01-005.txt, 01-006.txt, 01-007.txt, 01-008.txt, 01-009.txt, 01-010.txt, 01-011.txt, 01-012.txt, 01-013.txt, 01-014.txt, 01-015.txt, 01-016.txt, 01-017.txt, 01-018.txt, 01-019.txt, 01-020.txt, 01-021.txt, 01-022.txt, 01-023.txt, 01-024.txt, 01-025.txt, 01-026.txt, 01-027.txt, 01-028.txt, 01-029.txt, 01-030.txt, 01-031.txt, 01-032.txt, 01-033.txt, 01-034.txt, 01-035.txt, 01-036.txt, 01-037.txt, 01-038.txt, 01-039.txt, 01-040.txt, 01-041.txt, 01-042.txt, 01-043.txt, 01-044.txt, 01-045.txt, 01-046.txt, 01-047.txt, 01-048.txt, 01-049.txt, 01-050.txt
Case Name Status Exec Time Memory
00-sample-001.txt AC 72 ms 93288 KiB
00-sample-002.txt AC 72 ms 93016 KiB
01-003.txt AC 71 ms 93208 KiB
01-004.txt AC 72 ms 93208 KiB
01-005.txt AC 72 ms 93192 KiB
01-006.txt AC 73 ms 93148 KiB
01-007.txt AC 72 ms 93256 KiB
01-008.txt AC 72 ms 93004 KiB
01-009.txt AC 771 ms 261304 KiB
01-010.txt AC 93 ms 108664 KiB
01-011.txt AC 181 ms 126924 KiB
01-012.txt AC 241 ms 144668 KiB
01-013.txt AC 325 ms 173308 KiB
01-014.txt AC 794 ms 274988 KiB
01-015.txt AC 843 ms 302340 KiB
01-016.txt AC 1240 ms 356304 KiB
01-017.txt AC 833 ms 272948 KiB
01-018.txt AC 1078 ms 311256 KiB
01-019.txt AC 789 ms 316860 KiB
01-020.txt AC 803 ms 292064 KiB
01-021.txt AC 776 ms 269684 KiB
01-022.txt AC 783 ms 315228 KiB
01-023.txt AC 768 ms 317108 KiB
01-024.txt AC 1089 ms 310084 KiB
01-025.txt AC 776 ms 323096 KiB
01-026.txt AC 855 ms 308220 KiB
01-027.txt AC 835 ms 316764 KiB
01-028.txt AC 841 ms 345760 KiB
01-029.txt AC 792 ms 316716 KiB
01-030.txt AC 775 ms 317032 KiB
01-031.txt AC 925 ms 311380 KiB
01-032.txt AC 796 ms 270796 KiB
01-033.txt AC 914 ms 282720 KiB
01-034.txt AC 1350 ms 413832 KiB
01-035.txt AC 1377 ms 413884 KiB
01-036.txt AC 1314 ms 412700 KiB
01-037.txt AC 850 ms 279792 KiB
01-038.txt AC 854 ms 279848 KiB
01-039.txt AC 905 ms 288604 KiB
01-040.txt AC 903 ms 288516 KiB
01-041.txt AC 841 ms 279884 KiB
01-042.txt AC 879 ms 279692 KiB
01-043.txt AC 806 ms 281932 KiB
01-044.txt AC 874 ms 280040 KiB
01-045.txt AC 823 ms 282404 KiB
01-046.txt AC 875 ms 279944 KiB
01-047.txt AC 713 ms 259120 KiB
01-048.txt AC 736 ms 259492 KiB
01-049.txt AC 835 ms 278392 KiB
01-050.txt AC 814 ms 279052 KiB