Submission #934238

#	Time	Username	Problem	Language	Result	Execution time	Memory
934238		Muhammad_Aneeq	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	692 ms	20872 KiB

palindromic

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
using namespace std;
#define int long long
int mod=1e9+7,base=997;
int power(int x,int y)
{
  int res=1;
  while (y)
  {
    if (y&1)
      res=(res*x)%mod;
    x=(x*x)%mod;
    y>>=1;
  }
  return res;
}
inline void solve()
{
  string s;
  cin>>s;
  int n=s.size();
  int hash[n+1]={};
  for (int i=0;i<n;i++)
    hash[i+1]=((hash[i]*base)+(s[i]-'a'+1))%mod;
  int l=0,r=1,l1=n-1,r1=n;
  int ans=0,len=0;
  if (s.size()==1)
  {
    cout<<1<<endl;return;
  }
  while (r<=l1)
  {
    len++;
    int f=(hash[l]*power(base,len))%mod;
    f=(hash[r]-f+mod)%mod;
    int g=(hash[l1]*power(base,len))%mod;
    g=(hash[r1]-g+mod)%mod;
    if (f==g)
    {
      ans+=2;
      l=r;
      r1=l1;
      len=0;
      if (r1-l==1)
        ans++;
    }
    r++;
    l1--;
  }
  if (l+1!=r)
    ans++;
  cout<<ans<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    cin>>t;
    while (t--)
        solve();
}

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