(cache)Submission #64072401 - UNIQUE VISION Programming Contest 2025 Spring (AtCoder Beginner Contest 398)

Contest Duration: 2025-03-22(Sat) 21:00 - 2025-03-22(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #64072401

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 longest_palindromic_substring(S):
    # Step 1: 文字列を "#a#b#c#" のように変換（奇数長の回文を統一的に扱う）
    T = "#" + "#".join(S) + "#"
    n = len(T)
    # Step 2: Manacher法で最長回文の半径を求める
    P = [0] * n  # P[i] は i を中心とする回文の半径
    C, R = 0, 0  # C は回文の中心, R は右端
    for i in range(n):
        mirr = 2 * C - i  # i の左右対称の位置
        if i < R:
            P[i] = min(R - i, P[mirr])  # 既存の回文の範囲内なら制限する
        # 中心を拡張
        while i - P[i] - 1 >= 0 and i + P[i] + 1 < n and T[i - P[i] - 1] == T[i + P[i] + 1]:
            P[i] += 1
        # R を更新
        if i + P[i] > R:
            C, R = i, i + P[i]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

def longest_palindromic_substring(S):
    # Step 1: 文字列を "#a#b#c#" のように変換（奇数長の回文を統一的に扱う）
    T = "#" + "#".join(S) + "#"
    n = len(T)

    # Step 2: Manacher法で最長回文の半径を求める
    P = [0] * n  # P[i] は i を中心とする回文の半径
    C, R = 0, 0  # C は回文の中心, R は右端

    for i in range(n):
        mirr = 2 * C - i  # i の左右対称の位置
        if i < R:
            P[i] = min(R - i, P[mirr])  # 既存の回文の範囲内なら制限する

        # 中心を拡張
        while i - P[i] - 1 >= 0 and i + P[i] + 1 < n and T[i - P[i] - 1] == T[i + P[i] + 1]:
            P[i] += 1

        # R を更新
        if i + P[i] > R:
            C, R = i, i + P[i]

    # Step 3: 最長回文の取得
    max_len, center = max((P[i], i) for i in range(n))  # 最大値を持つ i を探す
    start = (center - max_len) // 2  # 元の S のインデックスに変換
    return max_len

def f(S):
    if S==S[::-1]:
        return True
    return False

S=input()
x=longest_palindromic_substring(S)
if f(S[-x:]):
    T=S[:-x]
    print(S+T[::-1])
        
else:
    x=1
    T=S[:-x]
    print(S+T[::-1])

Submission Info

Submission Time	2025-03-22 21:43:17
Task	F - ABCBA
User	kotafuku
Language	Python (PyPy 3.10-v7.3.12)
Score	0
Code Size	1280 Byte
Status	WA
Exec Time	117 ms
Memory	97760 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 500

Status

× 3

AC	× 31
WA	× 5

Set Name	Test Cases
Sample	sample_01.txt, sample_02.txt, sample_03.txt
All	sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt

Case Name	Status	Exec Time	Memory
sample_01.txt	AC	57 ms	76436 KiB
sample_02.txt	AC	59 ms	76488 KiB
sample_03.txt	AC	58 ms	76176 KiB
test_01.txt	AC	58 ms	76472 KiB
test_02.txt	AC	59 ms	76608 KiB
test_03.txt	AC	60 ms	76264 KiB
test_04.txt	AC	59 ms	76620 KiB
test_05.txt	AC	58 ms	76580 KiB
test_06.txt	AC	58 ms	76648 KiB
test_07.txt	AC	59 ms	76200 KiB
test_08.txt	AC	58 ms	76392 KiB
test_09.txt	AC	59 ms	76508 KiB
test_10.txt	AC	110 ms	97596 KiB
test_11.txt	AC	110 ms	97152 KiB
test_12.txt	AC	111 ms	97448 KiB
test_13.txt	WA	111 ms	97444 KiB
test_14.txt	AC	113 ms	97176 KiB
test_15.txt	AC	114 ms	97456 KiB
test_16.txt	WA	111 ms	97488 KiB
test_17.txt	AC	110 ms	97248 KiB
test_18.txt	AC	110 ms	97488 KiB
test_19.txt	AC	114 ms	97428 KiB
test_20.txt	AC	116 ms	97612 KiB
test_21.txt	WA	111 ms	97604 KiB
test_22.txt	AC	117 ms	97760 KiB
test_23.txt	AC	110 ms	97488 KiB
test_24.txt	AC	108 ms	97332 KiB
test_25.txt	AC	109 ms	97236 KiB
test_26.txt	WA	114 ms	97616 KiB
test_27.txt	AC	110 ms	97608 KiB
test_28.txt	AC	113 ms	97612 KiB
test_29.txt	AC	110 ms	97408 KiB
test_30.txt	AC	115 ms	97444 KiB
test_31.txt	WA	111 ms	97432 KiB
test_32.txt	AC	114 ms	97288 KiB
test_33.txt	AC	110 ms	97600 KiB