oj.uz

Submission #112113

# Submission time Handle Problem Language Result Execution time Memory
112113 2019-05-17T12:35:38 Z aleksami Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 22 ms 15992 KB 
#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);
  }
  return 1;
}

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);
  init();
  int t;
  cin >> t;
  while(t--)
  {
    solve();
  }
  return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 15992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 15992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 15992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 15992 KB Output isn't correct
2 Halted 0 ms 0 KB -