Submission details
Task:Longest palindrome
Sender:aalto25j_005
Submission time:2025-11-05 17:22:26 +0200
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#2ACCEPTED0.00 sdetails
#30.02 sdetails
#4ACCEPTED0.02 sdetails
#50.02 sdetails
#6ACCEPTED0.02 sdetails
#70.03 sdetails
#80.02 sdetails
#90.00 sdetails
#10ACCEPTED0.00 sdetails
#110.01 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#140.00 sdetails
#150.00 sdetails
#16ACCEPTED0.01 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for (int i = 0; i < res.size(); i++) {
      |                         ~~^~~~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define IOS ios_base::sync_with_stdio(0), cin.tie(0)
const int INF = 1001001001;
const int MAXN = 100'000;
const char br = '\n';
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
	{                                                                      \
		++recur_depth;                                                 \
		auto x_ = x;                                                   \
		--recur_depth;                                                 \
		cerr << string(recur_depth, '\t') << "\e[91m" << __func__      \
		     << ":" << __LINE__ << "\t" << #x << " = " << x_           \
		     << "\e[39m" << endl;                                      \
	}
#else
#define dbg(x)
#endif
template <typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream &>::type
operator<<(Ostream &os, const Cont &v) {
	os << "[";
	for (auto &x : v) {
		os << x << ", ";
	}
	return os << "]";
}

// === Debug macro ends here ===

// print pair, vector
template <typename Ostream, typename... Ts>
Ostream &operator<<(Ostream &os, const pair<Ts...> &p) {
	return os << "{" << p.first << ", " << p.second << "}";
}
template <typename T> ostream &operator<<(ostream &s, vector<T> t) {
	for (const T &v : t) {
		cout << v << " ";
	}
	return s;
}

int nxt() {
	int x;
	cin >> x;
	return x;
}

vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    int l = 0, r = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = min(r - i, p[l + (r - i)]);
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

vector<int> manacher(string s) {
    string t;
    for(auto c: s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}


int main() {
	IOS;

	string s;
	cin >> s;

	auto res = manacher_odd(s);

	int center = 0;
	int max = 0;
	for (int i = 0; i < res.size(); i++) {
		int num = res[i];
		if (num > max) {
			center = i;
			max = num;
		}
	}

	int len = max - 1;
	cout << s.substr(center - len, len * 2 + 1) << br;

	return 0;
}

Test details

Test 1

Verdict:

input
aaaaaaaaaa

correct output
aaaaaaaaaa

user output
aaaaaaaaa

Test 2

Verdict: ACCEPTED

input
ababababab

correct output
ababababa

user output
ababababa

Test 3

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

user output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
Truncated

Test 4

Verdict: ACCEPTED

input
ababababababababababababababab...

correct output
ababababababababababababababab...

user output
ababababababababababababababab...
Truncated

Test 5

Verdict:

input
aztdvxzjwxtrludymvpradgbdpgnrq...

correct output
aztdvxzjwxtrludymvpradgbdpgnrq...

user output
wuw

Test 6

Verdict: ACCEPTED

input
vvfigwwsyxbukedgcfyibvtbclybud...

correct output
vvfigwwsyxbukedgcfyibvtbclybud...

user output
vvfigwwsyxbukedgcfyibvtbclybud...
Truncated

Test 7

Verdict:

input
abaabaaaaaaabaababbbbbbabaaabb...

correct output
babbbabbbaabbbbaabbbbbbbbaabbb...

user output
bbbabaaababababbbbabbbbabababa...

Test 8

Verdict:

input
txolestmgyepwrpofxyesjtsfkhjac...

correct output
yxnbaabnxy

user output
xihypyhix

Test 9

Verdict:

input
ihpohpzoffel

correct output
ff

user output
i

Test 10

Verdict: ACCEPTED

input
flexflexvpqxierullgcfckjqflexf...

correct output
cfc

user output
cfc

Test 11

Verdict:

input
aabbabaabbaababbabaababbaabbab...

correct output
abaababbaabbabaababbabaabbaaba...

user output
bab

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:

input
zzabc

correct output
zz

user output
z

Test 15

Verdict:

input
aaccaabbaaccaaccaabbaaccaa

correct output
aaccaabbaaccaaccaabbaaccaa

user output
a

Test 16

Verdict: ACCEPTED

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

user output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
Truncated