Submission #112117

#	Time	Username	Problem	Language	Result	Execution time	Memory
112117		aleksami	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	167 ms	24980 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;
#define MAXN 1000005
typedef long long ll;
const ll p = 131;
const ll MOD = 1e9+7;
ll addmod(ll x,ll y)
{
  x+=y;
  x+=MOD;
  x%=MOD;
  return x;
}
ll mulmod(ll x,ll y)
{
  x*=y;
  x%=MOD;
  return x;
}

ll pw[MAXN];
ll invpw[MAXN];

ll fastpow(ll x,int s)
{
  if(s==0)return 1LL;
  if(s%2==0)
  {
    ll y = fastpow(x,s/2);
    return mulmod(y,y);
  }
  return mulmod(x,fastpow(x,s-1));
}

void init()
{
  pw[0]=1LL;
  for(int i = 1; i < MAXN; i++)pw[i]=mulmod(pw[i-1],p);
  invpw[0]=1LL;
  ll invp = fastpow(p,MOD-2);
  for(int i = 1; i < MAXN; i++)invpw[i]=mulmod(invpw[i-1],invp);
}
ll sum[MAXN];
string s;
int n;

ll geth(ll x,int s)
{
  return mulmod(x,pw[s]);
}
ll get(int l,int r)
{
  ll ret = sum[r];
  if(l>0)ret=addmod(ret,-sum[l-1]);
  ret=mulmod(ret,invpw[l]);
  return ret;
}

int solve(int left,int right)
{
  for(int d = 1; left+d-1 < right-d+1; d++)
  {
    if(get(left,left+d-1)==get(right-d+1,right))return 2+solve(left+d,right-d);
  }
  if(left <= right)return 1;
  return 0;
}

void solve()
{
  cin >> s;
  n = s.length();
  for(int i = 0; i < n; i++)
  {
    sum[i]=geth(s[i],i);
    if(i>0)sum[i]=addmod(sum[i],sum[i-1]);
  }
  cout << solve(0,n-1) << "\n";
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  init();
  int t;
  cin >> t;
  while(t--)
  {
    solve();
  }
  return 0;
}

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