(cache)Submission #64134345 - AtCoder Regular Contest 195 (Div. 2)

Contest Duration: 2025-03-23(Sun) 21:00 - 2025-03-23(Sun) 23:00 (local time) (120 minutes) Back to Home

Submission #64134345

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def f(A, B):
    BASE = 257
    MOD = 10**9 + 7 
    N, M = len(A), len(B)
    if M > N:
        return "No"
    hash_B = 0
    p = 1  
    for i in range(M):
        hash_B = (hash_B * BASE + B[i]) % MOD
        if i < M - 1:
            p = (p * BASE) % MOD 
            
    hash_A = 0
    for i in range(M):
        hash_A = (hash_A * BASE + A[i]) % MOD
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

def f(A, B):
    BASE = 257
    MOD = 10**9 + 7 

    N, M = len(A), len(B)
    if M > N:
        return "No"

    hash_B = 0
    p = 1  
    for i in range(M):
        hash_B = (hash_B * BASE + B[i]) % MOD
        if i < M - 1:
            p = (p * BASE) % MOD 

            
    hash_A = 0
    for i in range(M):
        hash_A = (hash_A * BASE + A[i]) % MOD


    seen = set()
    cnt = 0


    for i in range(N - M + 1):
        if hash_A == hash_B:
            cnt += 1
            if cnt >= 2:
                return "Yes"


        if i + M < N:
            hash_A = (hash_A * BASE - A[i] * p + A[i + M]) % MOD
            hash_A = (hash_A + MOD) % MOD

    return "No"


N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
print(f(A,B))

Submission Info

Submission Time	2025-03-23 21:13:29
Task	A - Twice Subsequence
User	kotafuku
Language	Python (PyPy 3.10-v7.3.12)
Score	0
Code Size	829 Byte
Status	WA
Exec Time	115 ms
Memory	138060 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 400

Status

AC	× 2
WA	× 1

AC	× 26
WA	× 22

Set Name	Test Cases
Sample	00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All	00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_handmade_01.txt, 01_handmade_02.txt, 01_handmade_03.txt, 01_handmade_04.txt, 01_handmade_05.txt, 02_small_01.txt, 02_small_02.txt, 02_small_03.txt, 02_small_04.txt, 02_small_05.txt, 03_medium_01.txt, 03_medium_02.txt, 03_medium_03.txt, 03_medium_04.txt, 03_medium_05.txt, 04_large_01.txt, 04_large_02.txt, 04_large_03.txt, 04_large_04.txt, 04_large_05.txt, 05_max_01.txt, 05_max_02.txt, 05_max_03.txt, 05_max_04.txt, 05_max_05.txt, 06_not_emerge_01.txt, 06_not_emerge_02.txt, 06_not_emerge_03.txt, 07_emerge_once_01.txt, 07_emerge_once_02.txt, 07_emerge_once_03.txt, 07_emerge_once_04.txt, 07_emerge_once_05.txt, 08_emerge_twice_01.txt, 08_emerge_twice_02.txt, 08_emerge_twice_03.txt, 08_emerge_twice_04.txt, 08_emerge_twice_05.txt, 09_one_two_only_01.txt, 09_one_two_only_02.txt, 09_one_two_only_03.txt, 09_one_two_only_04.txt, 09_one_two_only_05.txt, 09_one_two_only_06.txt, 09_one_two_only_07.txt

Case Name	Status	Exec Time	Memory
00_sample_01.txt	WA	59 ms	76680 KiB
00_sample_02.txt	AC	59 ms	76572 KiB
00_sample_03.txt	AC	59 ms	76552 KiB
01_handmade_01.txt	AC	59 ms	76692 KiB
01_handmade_02.txt	AC	115 ms	118280 KiB
01_handmade_03.txt	WA	101 ms	137996 KiB
01_handmade_04.txt	AC	99 ms	138060 KiB
01_handmade_05.txt	AC	100 ms	137460 KiB
02_small_01.txt	AC	59 ms	76404 KiB
02_small_02.txt	WA	59 ms	76368 KiB
02_small_03.txt	WA	60 ms	76464 KiB
02_small_04.txt	WA	61 ms	76504 KiB
02_small_05.txt	AC	61 ms	76556 KiB
03_medium_01.txt	AC	60 ms	76536 KiB
03_medium_02.txt	AC	59 ms	76504 KiB
03_medium_03.txt	WA	60 ms	76704 KiB
03_medium_04.txt	AC	60 ms	76768 KiB
03_medium_05.txt	WA	60 ms	76556 KiB
04_large_01.txt	AC	67 ms	83300 KiB
04_large_02.txt	WA	99 ms	114668 KiB
04_large_03.txt	AC	113 ms	116324 KiB
04_large_04.txt	WA	82 ms	102600 KiB
04_large_05.txt	WA	100 ms	118596 KiB
05_max_01.txt	WA	114 ms	117988 KiB
05_max_02.txt	WA	113 ms	116688 KiB
05_max_03.txt	AC	114 ms	117740 KiB
05_max_04.txt	WA	114 ms	117060 KiB
05_max_05.txt	AC	115 ms	116616 KiB
06_not_emerge_01.txt	AC	90 ms	114192 KiB
06_not_emerge_02.txt	AC	91 ms	114180 KiB
06_not_emerge_03.txt	AC	91 ms	114228 KiB
07_emerge_once_01.txt	AC	99 ms	119520 KiB
07_emerge_once_02.txt	AC	115 ms	117016 KiB
07_emerge_once_03.txt	AC	105 ms	117824 KiB
07_emerge_once_04.txt	AC	114 ms	116416 KiB
07_emerge_once_05.txt	AC	89 ms	114184 KiB
08_emerge_twice_01.txt	WA	97 ms	119560 KiB
08_emerge_twice_02.txt	WA	111 ms	115748 KiB
08_emerge_twice_03.txt	WA	104 ms	117728 KiB
08_emerge_twice_04.txt	WA	104 ms	117824 KiB
08_emerge_twice_05.txt	WA	107 ms	118308 KiB
09_one_two_only_01.txt	AC	92 ms	122488 KiB
09_one_two_only_02.txt	WA	92 ms	122588 KiB
09_one_two_only_03.txt	WA	91 ms	120712 KiB
09_one_two_only_04.txt	WA	90 ms	119196 KiB
09_one_two_only_05.txt	AC	96 ms	128584 KiB
09_one_two_only_06.txt	WA	85 ms	111280 KiB
09_one_two_only_07.txt	AC	93 ms	123988 KiB