Submission #154316

#	Time	Username	Problem	Language	Result	Execution time	Memory
154316		arnold518	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	239 ms	34644 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;
const ll MOD = 1e9+7;
const ll P = 31;

int TC, N, ans;
char S[MAXN+10];
ll ppow[MAXN+10], ipow[MAXN+10], H[MAXN+10];

ll mypow(ll x, ll y)
{
    if(y==0) return 1;
    if(y%2) return mypow(x, y-1)*x%MOD;
    ll t=mypow(x, y/2);
    return t*t%MOD;
}

ll calc(int l, int r)
{
    ll t=H[r]-H[l-1]; t%=MOD;
    if(t<0) t+=MOD;
    t*=ipow[l]; t%=MOD;
    return t;
}

int main()
{
    int i, j;

    ppow[0]=1; ipow[0]=1; ipow[1]=mypow(P, MOD-2);
    for(i=1; i<=MAXN; i++) ppow[i]=ppow[i-1]*P%MOD;
    for(i=2; i<=MAXN; i++) ipow[i]=ipow[i-1]*ipow[1]%MOD;

    scanf("%d", &TC);
    while(TC--)
    {
        scanf("%s", S+1);
        N=strlen(S+1); ans=0;

        for(i=1; i<=N; i++) H[i]=(S[i]-'a'+1)*ppow[i]%MOD;
        for(i=1; i<=N; i++) H[i]=(H[i-1]+H[i])%MOD;

        int it=1;
        for(i=1; i<=N/2; i++) if(calc(it, i)==calc(N-i+1, N-it+1))
        {
            //printf("!%d\n", i);
            ans+=2;
            it=i+1;
        }
        if(N%2 || it!=N/2+1) ans++;
        printf("%d\n", ans);
    }
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:34:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
palindromic.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &TC);
     ~~~~~^~~~~~~~~~~
palindromic.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", S+1);
         ~~~~~^~~~~~~~~~~

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