Longest palindrome

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<ll> vi;
typedef pair<ll,ll> pl;

#define F first
#define S second
#define PB push_back
#define MP make_pair

#define REP(i,a,b) for (ll i = a; i < b; i++)
#define rep(i,a,b) for (int i = a; i < b; i++)
#define sz(x) (int)(x).size()

array<vi, 2> manacher(const string& s) {
    int n = sz(s);
    array<vi,2> p = {vi(n+1), vi(n)};
    rep(z,0,2) for (int i=0,l=0,r=0; i < n; i++) {
        int t = r-i+!z;
        if (i<r) p[z][i] = min(t, (int)p[z][l+t]);
        int L = i-p[z][i], R = i+p[z][i]-!z;
        while (L>=1 && R+1<n && s[L-1] == s[R+1])
        p[z][i]++, L--, R++;
        if (R>r) l=L, r=R;
    }
    return p;
}

int main() {
    string s;
    cin >> s;

    array<vi, 2> p;

    p = manacher(s);


    ll max_p = 0;
    ll id = 0;
    bool even = true;
    REP(i,0,(ll)s.size()) {
        if(p[0][i] > max_p) {
            even = true;
            max_p = p[0][i];
            id = i;
        }
        if(p[1][i] >= max_p) {
            even = false;
            max_p = p[1][i];
            id = i;
        }
        //cout << p[0][i]  << " ";
    }

    //cout << "max_p " << max_p << " id " << id << endl;

    ll plus = 0;
    if(even) plus = -1;
    assert(id+max_p+plus<(ll)s.size());
    REP(i,id-max_p,id+max_p+plus+1) {
        cout << s[i];
    }
    cout << endl;
    
    
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED