Cod sursa(job #3290907)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 1 aprilie 2025 20:10:18
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#ifndef LOCAL
    #pragma GCC optimize("O3")
    // #pragma GCC target("avx2")
#endif

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

using namespace std;

/*******************************/
// INPUT / OUTPUT

#ifndef LOCAL
    ifstream in("pscpld.in");
    ofstream out("pscpld.out");
    #define cin in
    #define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS

string s;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    cin >> s;
}
///-------------------------------------
inline string get_manacher_string(string s)
{
    string nou = "!";
    for (int i = 0 ; i < s.length() - 1 ; ++ i)
    {
        nou += s[i];
        nou += "#";
    }
    nou += s[s.length() - 1];
    nou += ".";

    return nou;
}
///-------------------------------------
inline vector <int> get_manacher(string s)
{
    int N = s.length();
    vector <int> m(N, 0);

    m[0] = 1;
    while (m[1] + 1 < N && 1 - m[1] >= 0 && s[m[1] + 1] == s[1 - m[1]]) m[1] ++;
    
    int mij = 1, capat_dr = 1 + m[1];
    for (int i = 2 ; i < N ; ++ i)
    {
        m[i] = min(m[mij - (i - mij)], capat_dr - i);

        while (i + m[i] < N && i - m[i] >= 0 && s[m[i] + i] == s[i - m[i]]) m[i] ++;

        if (i + m[i] > capat_dr)
        {
            mij = i;
            capat_dr = i + m[i];
        }
    }

    return m;
}
///-------------------------------------
inline int get_palindrome_count(vector <int> m)
{
    int cnt = 0;
    for (int i = 0 ; i < m.size() ; ++ i)
    {
        if (i % 2 == 0) cnt += m[i] / 2;
        else cnt += (m[i] + 1) / 2;
    }

    return cnt;
}
///-------------------------------------
inline void Solution()
{
    s = get_manacher_string(s);
    auto m = get_manacher(s);
    cout << get_palindrome_count(m);
}
///-------------------------------------
inline void Output()
{

}
///-------------------------------------
signed main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    Output();
    return 0;
}