Submission #1095047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095047		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	94 ms	23352 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
long long n,m,base=311,k,t,mod=1e9+7,has[1000005],p[1000005];
long long get(long long x,long long y)
{
  return (has[y]-has[x-1]*p[y-x+1]+mod*mod)%mod;
}
string s;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>t;
  while(t--)
  {
  long long ans=0;
  cin>>s;
  n=s.length();
  s=' '+s;
  p[0]=1;
  for(int i=1;i<=n;i++)
   {
     p[i]=(p[i-1]*base)%mod;
     has[i]=(has[i-1]*base+s[i]-'a'+1)%mod;
   }
  long long neil=1,nei=n;
  for(int i=1;i<=n/2;i++)
  {
    if(get(neil,i)==get(nei-(i-neil),nei)) ans+=2,neil=i+1,nei=n-i;
  }
  if(neil<=nei) ans++;
  cout<<ans<<'\n';
  }
}

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