Submission details
Task:Longest palindrome
Sender:aalto26iw_006
Submission time:2026-11-04 16:20:57 +0200
Language:Rust (2021)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.05 sdetails
#4ACCEPTED0.05 sdetails
#5ACCEPTED0.05 sdetails
#6ACCEPTED0.05 sdetails
#7ACCEPTED0.05 sdetails
#8ACCEPTED0.04 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.01 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.02 sdetails

Code

#![allow(unused)]

use std::collections::*;
use std::io;

fn take_string() -> (Vec<char>, Vec<u8>) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let vec: Vec<u8> = input.trim().as_bytes().to_vec();
    (input.trim().chars().collect(), vec)
}

fn manacher(s: &Vec<u8>) -> Vec<usize> {
    let n = 2 * s.len() + 3;
    let mut ms: Vec<u8> = Vec::with_capacity(n);
    let mut p: Vec<usize> = vec![0; n];
    let (mut l, mut r) = (0usize, 0usize);
    ms.push(b'@');
    for i in 0..s.len() { ms.push(b'#'); ms.push(s[i]); }
    ms.push(b'#');
    ms.push(b'$');

    for i in 1..n - 1 {
        p[i] = if i < r { p[l + r - i].min(r - i) } else { 0 };
        while ms[i + 1 + p[i]] == ms[i - 1 - p[i]]{
            p[i] += 1;
        }
        if i + p[i] > r { l = i - p[i]; r = i + p[i]; }
    }
    p
}

fn longest_palindrome(s: &Vec<u8>) -> (usize, usize) {
    let pal = manacher(s);
    let mut best = (0, 0);
    for (c, &len) in pal.iter().enumerate() {
        if len > best.1 {
            best = ((c - len - 1) / 2, len);
        }
    }
    best
}

fn main() {
    let (_, s) = take_string();
    let (start, len) = longest_palindrome(&s);
    println!("{}", std::str::from_utf8(&s[start..start + len]).unwrap());
}

Test details

Test 1

Verdict: ACCEPTED

input
aaaaaaaaaa

correct output
aaaaaaaaaa

user output
aaaaaaaaaa

Test 2

Verdict: ACCEPTED

input
ababababab

correct output
ababababa

user output
ababababa

Test 3

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

user output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

Test 4

Verdict: ACCEPTED

input
ababababababababababababababab...

correct output
ababababababababababababababab...

user output
ababababababababababababababab...

Test 5

Verdict: ACCEPTED

input
aztdvxzjwxtrludymvpradgbdpgnrq...

correct output
aztdvxzjwxtrludymvpradgbdpgnrq...

user output
aztdvxzjwxtrludymvpradgbdpgnrq...

Test 6

Verdict: ACCEPTED

input
vvfigwwsyxbukedgcfyibvtbclybud...

correct output
vvfigwwsyxbukedgcfyibvtbclybud...

user output
vvfigwwsyxbukedgcfyibvtbclybud...

Test 7

Verdict: ACCEPTED

input
abaabaaaaaaabaababbbbbbabaaabb...

correct output
babbbabbbaabbbbaabbbbbbbbaabbb...

user output
babbbabbbaabbbbaabbbbbbbbaabbb...

Test 8

Verdict: ACCEPTED

input
txolestmgyepwrpofxyesjtsfkhjac...

correct output
yxnbaabnxy

user output
yxnbaabnxy

Test 9

Verdict: ACCEPTED

input
ihpohpzoffel

correct output
ff

user output
ff

Test 10

Verdict: ACCEPTED

input
flexflexvpqxierullgcfckjqflexf...

correct output
cfc

user output
cfc

Test 11

Verdict: ACCEPTED

input
aabbabaabbaababbabaababbaabbab...

correct output
abaababbaabbabaababbabaabbaaba...

user output
abaababbaabbabaababbabaabbaaba...

Test 12

Verdict: ACCEPTED

input
obsession

correct output
ses

user output
ses

Test 13

Verdict: ACCEPTED

input
abcxcbaxcba

correct output
abcxcba

user output
abcxcba

Test 14

Verdict: ACCEPTED

input
zzabc

correct output
zz

user output
zz

Test 15

Verdict: ACCEPTED

input
aaccaabbaaccaaccaabbaaccaa

correct output
aaccaabbaaccaaccaabbaaccaa

user output
aaccaabbaaccaaccaabbaaccaa

Test 16

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

user output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...