Submission #482931

#	Time	Username	Problem	Language	Result	Execution time	Memory
482931		MohamedAliSaidane	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	1041 ms	29000 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> ti;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ld,ld> pld;
#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front
#define ff first
#define ss second
#define MOD (ll)(1000000007)
#define INF (ll) (1e18)
#define all(v) (v).begin(),(v).end()
const int nx[8] = {0, 0, 1, -1,1,1,-1,-1}, ny[8] = {1, -1, 0, 0,1,-1,1,-1}; //East, West, South, North+
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}

ll mod(ll a, ll m)
{
    return ((a%m)+m)%m;
}
ll modInverse(ll a, ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;
    if (m == 1)
        return 0;
    while (a > 1) {
        ll q = a / m;
        ll t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0)
        x += m0;
    return x;
}
////////////******SOLUTION******\\\\\\\\\\\

string s, t;
int n;
ll p = 131ll;
vll P;
vll h;
ll hash_fast(int l, int r)
{
    if(l == 0)
        return h[r];
    ll ans = 0;
    ans = ((h[r] - h[l-1])%MOD + MOD)%MOD;
    ans = ((ll)ans*modInverse(P[l],MOD))%MOD;
    //cout << "here\n" << flush;
    return ans;
}
void solve()
{
    cin >> s;
    n = s.length();
    P.assign(n,0ll);
    P[0] = 1ll;
    h.assign(n,0ll);
    for(int i = 1;i <n; i++)
    {
        P[i] = ((ll)(P[i-1]*p))% MOD;
    }
    for(int i = 0; i < n; i ++)
    {
        if(i != 0)
        h[i] = h[i-1];
        h[i] = (h[i]+((ll)s[i]*P[i])%MOD)%MOD;
        //cout << h[i] << ' ';
    }
    //cout << '\n';
    int ans = 0;
    int i = 0;
    while(i <= n/2-1 + n%2)
    {
        //cout << i << ' ' << flush;
        if(s[i] != s[n-i-1])
        {
            int u = 1;
            ll pr = hash_fast(i,i+u);
            ll dup = hash_fast(n-i-u-1,n-i-1);
            while(pr != dup)
            {
                u ++;
                pr = hash_fast(i,i+u);
                dup = hash_fast(n-i-u-1,n-i-1);
            }
            i += u;
        }
        ans += 2;
        if(i >= n/2)
            ans --;
        i ++;
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tt; cin >> tt;
    while(tt--)
        solve();
}

Compilation message (stderr)

palindromic.cpp:46:1: warning: multi-line comment [-Wcomment]
   46 | ////////////******SOLUTION******\\\\\\\\\\\
      | ^

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40