Submission #141315

#	Time	Username	Problem	Language	Result	Execution time	Memory
141315		rzbt	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	165 ms	26712 KiB

palindromic

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 1000006
typedef long long ll;
const ll MOD = 1e9 + 7;
using namespace std;

char s[MAXN];
ll n;
ll p[MAXN];
ll hes[MAXN];
void hesuj(){
    p[0]=1;
    hes[1]=s[0]-'a';
    for(int i=1;i<n;i++){
        p[i]=(p[i-1]*37)%MOD;
        hes[i+1]=(hes[i]+p[i]*(s[i]-'a'))%MOD;
    }
}

int main()
{
    int ttt;
    scanf("%d",&ttt);
    while(ttt--){
        scanf("%s",s);
        n=strlen(s);
        int l=0,d=n-1,pl=0,pd=n-1,res=0;

        hesuj();
        while(l<=d){
            if(pl==pd)break;
            if(((MOD+hes[l+1]-hes[pl])*p[d])%MOD==((MOD-hes[d]+hes[pd+1])*p[pl])%MOD){
                res+=2;
                pl=l+1;
                pd=d-1;
            }

            l++;
            d--;
        }
        if(pl>pd)printf("%d\n",res);
        else{
            printf("%d\n",res+1);

        }

    }

    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&ttt);
     ~~~~~^~~~~~~~~~~
palindromic.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",s);
         ~~~~~^~~~~~~~

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