| Task: | Longest palindrome |
| Sender: | aalto26iw_001 |
| Submission time: | 2026-11-04 17:16:20 +0200 |
| Language: | C++ (C++20) |
| Status: | READY |
| Result: | TIME LIMIT EXCEEDED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | details |
| #2 | ACCEPTED | 0.00 s | details |
| #3 | TIME LIMIT EXCEEDED | -- | details |
| #4 | TIME LIMIT EXCEEDED | -- | details |
| #5 | TIME LIMIT EXCEEDED | -- | details |
| #6 | TIME LIMIT EXCEEDED | -- | details |
| #7 | TIME LIMIT EXCEEDED | -- | details |
| #8 | TIME LIMIT EXCEEDED | -- | details |
| #9 | ACCEPTED | 0.00 s | details |
| #10 | ACCEPTED | 0.00 s | details |
| #11 | TIME LIMIT EXCEEDED | -- | details |
| #12 | ACCEPTED | 0.00 s | details |
| #13 | ACCEPTED | 0.00 s | details |
| #14 | ACCEPTED | 0.00 s | details |
| #15 | ACCEPTED | 0.00 s | details |
| #16 | TIME LIMIT EXCEEDED | -- | details |
Compiler report
input/code.cpp: In function 'std::string longestPalindrome(std::string, std::string)':
input/code.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | while (center < r.length())
| ~~~~~~~^~~~~~~~~~~~
input/code.cpp:118:68: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | while (center - (radius + 1) >= 0 && center + (radius + 1) < r.length() && r[center - (radius + 1)] == r[center + (radius + 1)])
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
input/code.cpp:151:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for (int i = 0; i < palindromeLengt...Code
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
class Manacher {
public:
// p[i] = radius of longest palindrome centered at i
// in transformed string
vector<int> p;
// transformed string with # and sentinels
string ms;
// preprocess the string and run the algorithm
Manacher(string &s) {
// left sentinel
ms = "@";
for (char c : s) {
ms += "#" + string(1, c);
}
// right sentinel
ms += "#$";
// run Manacher’s algorithm
runManacher();
}
void runManacher() {
int n = ms.size();
p.assign(n, 0);
int l = 0, r = 0;
for (int i = 1; i < n - 1; ++i) {
// mirror of i around center (l + r)/2
int mirror = l + r - i;
// initialize p[i] based on its mirror
// if within bounds
if (i < r)
p[i] = min(r - i, p[mirror]);
// expand palindrome centered at i
while (ms[i + 1 + p[i]] == ms[i - 1 - p[i]]){
++p[i];
}
// update [l, r] if the palindrome expands
// beyond current r
if (i + p[i] > r) {
l = i - p[i];
r = i + p[i];
}
}
}
// returns length of longest palindrome centered
// at 'cen' in original string
// 'odd' = 1 → check for odd-length, 'odd' = 0 → even-length
int getLongest(int cen, int odd) {
// map original index to transformed string index
int pos = 2 * cen + 2 + !odd;
return p[pos];
}
// checks if s[l..r] is a palindrome in O(1)
bool check(int l, int r) {
int len = r - l + 1;
int cen = (l + r) / 2;
return len <= getLongest(cen, len % 2);
}
};
string longestPalindrome(string s) {
Manacher mob(s);
int n = s.size();
// maximum length found so far
int maxLen = 1;
// starting index of longest palindrome
int bestStart = 0;
for (int i = 0; i < n; i++) {
// check for odd-length palindrome centered at i
int oddLen = mob.getLongest(i, 1);
if (oddLen > maxLen) {
maxLen = oddLen;
bestStart = i - maxLen / 2;
}
// check for even-length palindrome centered
// between i and i+1
int evenLen = mob.getLongest(i, 0);
if (evenLen > maxLen) {
maxLen = evenLen;
bestStart = i - maxLen / 2 + 1;
}
}
// extract the longest palindromic substring
return s.substr(bestStart, maxLen);
}
string longestPalindrome(string s, string r)
{
vector<int> palindromeLengths(r.length(), 0);
int center = 0;
int radius = 0;
while (center < r.length())
{
while (center - (radius + 1) >= 0 && center + (radius + 1) < r.length() && r[center - (radius + 1)] == r[center + (radius + 1)])
{
radius++;
}
palindromeLengths[center] = radius;
int oldCenter = center;
int oldRadius = radius;
center++;
radius = 0;
while (center <= oldCenter + oldRadius)
{
int mirroredCenter = oldCenter - (center - oldCenter);
int maxMirroredRadius = oldCenter + oldRadius - center;
if (palindromeLengths[mirroredCenter] < maxMirroredRadius)
{
palindromeLengths[center] = palindromeLengths[mirroredCenter];
center++;
}
else if (palindromeLengths[mirroredCenter] > maxMirroredRadius)
{
palindromeLengths[center] = maxMirroredRadius;
center++;
}
else
{
radius = maxMirroredRadius;
break;
}
}
}
int maxCenter = 0;
int maxLength = 0;
for (int i = 0; i < palindromeLengths.size(); i++)
{
if (palindromeLengths[i] > maxLength)
{
maxLength = palindromeLengths[i];
maxCenter = i;
}
}
string result;
for (int i = (maxCenter) - (maxLength); i < maxCenter + maxLength; i++)
{
if (r[i] != '#')
{
result += r[i];
}
}
return result;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string s, t;
cin >> s;
string r = "#";
for (int i = 0; i < s.size(); i++)
{
r = r + s[i] + '#';
}
cout << longestPalindrome(s) << endl;
}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: TIME LIMIT EXCEEDED
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| user output |
|---|
| (empty) |
Test 4
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| ababababababababababababababab... |
| correct output |
|---|
| ababababababababababababababab... |
| user output |
|---|
| (empty) |
Test 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| aztdvxzjwxtrludymvpradgbdpgnrq... |
| correct output |
|---|
| aztdvxzjwxtrludymvpradgbdpgnrq... |
| user output |
|---|
| (empty) |
Test 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| vvfigwwsyxbukedgcfyibvtbclybud... |
| correct output |
|---|
| vvfigwwsyxbukedgcfyibvtbclybud... |
| user output |
|---|
| (empty) |
Test 7
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| abaabaaaaaaabaababbbbbbabaaabb... |
| correct output |
|---|
| babbbabbbaabbbbaabbbbbbbbaabbb... |
| user output |
|---|
| (empty) |
Test 8
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| txolestmgyepwrpofxyesjtsfkhjac... |
| correct output |
|---|
| yxnbaabnxy |
| user output |
|---|
| (empty) |
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: TIME LIMIT EXCEEDED
| input |
|---|
| aabbabaabbaababbabaababbaabbab... |
| correct output |
|---|
| abaababbaabbabaababbabaabbaaba... |
| user output |
|---|
| (empty) |
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: TIME LIMIT EXCEEDED
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| user output |
|---|
| (empty) |
