CSES - Aalto Competitive Programming 2024 - wk9 - Wed - Results
Submission details
Task:Longest palindrome
Sender:aalto2024j_001
Submission time:2024-11-06 16:34:23 +0200
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.03 sdetails
#4ACCEPTED0.03 sdetails
#5ACCEPTED0.03 sdetails
#6ACCEPTED0.03 sdetails
#7ACCEPTED0.04 sdetails
#8ACCEPTED0.03 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

#include <bits/stdc++.h>

using namespace std;

//Definitions for quicker writing
#define REP(i,a,b) for (int i = a; i < b; i++)
#define clz __builtin_clz
#define ctz __builtin_ctz
#define popct __builtin_popcount
#define PB push_back
#define MP make_pair
#define F first
#define S second

//Typedefs for quicker writing
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
typedef pair<long long, long long> pl;

//Max values
const long long lmx = LLONG_MAX;
const int imx = INT_MAX;
string s;

string manacher() {  
    string T = "#";  
    for (char c : s) {  
        T += c;  
        T += '#';  
    }  
    int n = T.length();  
    vector<int> P(n, 0);  
    int C = 0, R = 0;  
    for (int i = 0; i < n; i++) {  
        int mirr = 2 * C - i;  
        if (i < R)  
            P[i] = min(R - i, P[mirr]);  

        int a = i + (1 + P[i]);  
        int b = i - (1 + P[i]);  
        while (a < n && b >= 0 && T[a] == T[b]) {  
            P[i]++;  
            a++;  
            b--;  
        }  

        if (i + P[i] > R) {  
            C = i;  
            R = i + P[i];  
        }  
    }  
    int maxLen = *max_element(P.begin(), P.end());  
    int centerIndex = find(P.begin(), P.end(), maxLen) - P.begin();  
    int start = (centerIndex - maxLen) / 2;  
    return s.substr(start, maxLen);  
}  


int main() {
	//IO optimization
	ios::sync_with_stdio(0);
	cin.tie(0);

	//Read In
	cin >> s;

	//Main part
	
    string res = manacher();
	
	//Write out
	cout << res << "\n";
		
	//Return
	return 0;

}

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...