oj.uz

Submission #154314

# Submission time Handle Problem Language Result Execution time Memory
154314 2019-09-20T12:27:21 Z arnold518 Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 27 ms 16092 KB 
#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=1;

        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))
        {
            if(i!=N-i+1) ans+=2;
            else ans++;

            it=i+1;
        }
        printf("%d\n", ans);
    }
}

Compilation message

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
0 / 15.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

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