| Task: | Longest palindrome |
| Sender: | aalto26iw_003 |
| Submission time: | 2026-11-04 16:24:35 +0200 |
| Language: | Python3 (PyPy3) |
| Status: | READY |
| Result: | WRONG ANSWER |
| test | verdict | time | |
|---|---|---|---|
| #1 | WRONG ANSWER | 0.05 s | details |
| #2 | WRONG ANSWER | 0.05 s | details |
| #3 | WRONG ANSWER | 0.28 s | details |
| #4 | WRONG ANSWER | 0.28 s | details |
| #5 | WRONG ANSWER | 0.31 s | details |
| #6 | WRONG ANSWER | 0.31 s | details |
| #7 | WRONG ANSWER | 0.31 s | details |
| #8 | WRONG ANSWER | 0.27 s | details |
| #9 | WRONG ANSWER | 0.05 s | details |
| #10 | WRONG ANSWER | 0.05 s | details |
| #11 | WRONG ANSWER | 0.12 s | details |
| #12 | WRONG ANSWER | 0.05 s | details |
| #13 | WRONG ANSWER | 0.05 s | details |
| #14 | WRONG ANSWER | 0.05 s | details |
| #15 | WRONG ANSWER | 0.05 s | details |
| #16 | WRONG ANSWER | 0.15 s | details |
Code
# FULL TEMPLATE: delete every block you don't use. Blocks don't depend on each other.
# Nodes are 1..n (slot 0 unused). Arrays are 0-indexed.
import sys
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from itertools import accumulate, permutations, combinations, product
from functools import lru_cache, cmp_to_key
from math import gcd, isqrt, comb, inf
input = sys.stdin.readline
MOD = 10**9 + 7
def I(): return int(input()) # "5" -> 5
def MI(): return map(int, input().split()) # "8 4" -> n, q = MI()
def LI(): return list(map(int, input().split())) # "3 2 4 5" -> [3, 2, 4, 5]
def S(): return input().strip() # "BABAZA", ".*.#" (kept as text)
def LS(): return input().split() # "? 2 3" -> ['?', '2', '3']
def manacher(s): # -> p on t = "#a#b#a#": p[i] = radius in t = LENGTH of the palindrome in s
t = "#" + "#".join(s) + "#" # every palindrome in t has odd length: one case only
n = len(t)
p = [0] * n
c = r = 0 # palindrome t[c-p[c] .. c+p[c]] reaches furthest right (r)
for i in range(n):
if i < r:
p[i] = min(r - i, p[2 * c - i]) # mirror image of i around c
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
if i + p[i] > r:
c, r = i, i + p[i]
return p
def longest_palindrome(s):
p = manacher(s)
i = max(range(len(p)), key=p.__getitem__)
start = (i - p[i]) // 2
return s[start:start + p[i]]
def main():
s = S()
p = manacher(s)
i = max(range(len(p)), key=p.__getitem__)
start = (i - p[i]) // 2
return s[start:start + p[i]]
main()
Test details
Test 1
Verdict: WRONG ANSWER
| input |
|---|
| aaaaaaaaaa |
| correct output |
|---|
| aaaaaaaaaa |
| user output |
|---|
| (empty) |
Test 2
Verdict: WRONG ANSWER
| input |
|---|
| ababababab |
| correct output |
|---|
| ababababa |
| user output |
|---|
| (empty) |
Test 3
Verdict: WRONG ANSWER
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| user output |
|---|
| (empty) |
Test 4
Verdict: WRONG ANSWER
| input |
|---|
| ababababababababababababababab... |
| correct output |
|---|
| ababababababababababababababab... |
| user output |
|---|
| (empty) |
Test 5
Verdict: WRONG ANSWER
| input |
|---|
| aztdvxzjwxtrludymvpradgbdpgnrq... |
| correct output |
|---|
| aztdvxzjwxtrludymvpradgbdpgnrq... |
| user output |
|---|
| (empty) |
Test 6
Verdict: WRONG ANSWER
| input |
|---|
| vvfigwwsyxbukedgcfyibvtbclybud... |
| correct output |
|---|
| vvfigwwsyxbukedgcfyibvtbclybud... |
| user output |
|---|
| (empty) |
Test 7
Verdict: WRONG ANSWER
| input |
|---|
| abaabaaaaaaabaababbbbbbabaaabb... |
| correct output |
|---|
| babbbabbbaabbbbaabbbbbbbbaabbb... |
| user output |
|---|
| (empty) |
Test 8
Verdict: WRONG ANSWER
| input |
|---|
| txolestmgyepwrpofxyesjtsfkhjac... |
| correct output |
|---|
| yxnbaabnxy |
| user output |
|---|
| (empty) |
Test 9
Verdict: WRONG ANSWER
| input |
|---|
| ihpohpzoffel |
| correct output |
|---|
| ff |
| user output |
|---|
| (empty) |
Test 10
Verdict: WRONG ANSWER
| input |
|---|
| flexflexvpqxierullgcfckjqflexf... |
| correct output |
|---|
| cfc |
| user output |
|---|
| (empty) |
Test 11
Verdict: WRONG ANSWER
| input |
|---|
| aabbabaabbaababbabaababbaabbab... |
| correct output |
|---|
| abaababbaabbabaababbabaabbaaba... |
| user output |
|---|
| (empty) |
Test 12
Verdict: WRONG ANSWER
| input |
|---|
| obsession |
| correct output |
|---|
| ses |
| user output |
|---|
| (empty) |
Test 13
Verdict: WRONG ANSWER
| input |
|---|
| abcxcbaxcba |
| correct output |
|---|
| abcxcba |
| user output |
|---|
| (empty) |
Test 14
Verdict: WRONG ANSWER
| input |
|---|
| zzabc |
| correct output |
|---|
| zz |
| user output |
|---|
| (empty) |
Test 15
Verdict: WRONG ANSWER
| input |
|---|
| aaccaabbaaccaaccaabbaaccaa |
| correct output |
|---|
| aaccaabbaaccaaccaabbaaccaa |
| user output |
|---|
| (empty) |
Test 16
Verdict: WRONG ANSWER
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| user output |
|---|
| (empty) |
