Submission #99933

#	Time	Username	Problem	Language	Result	Execution time	Memory
99933		pavel	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	92 ms	14940 KiB

palindromic

#include <cstdio>
#include <cstring>

using namespace std;
typedef long long ll;

const int MAXN = 1000006;
const int MOD = 1000000007;
const int BASE = 34;

int n;
char str[MAXN];
int p[MAXN];

int ADD(ll a, ll b){
    return (a+b)%MOD;
}

int MUL(ll a, ll b){
    return a*b%MOD;
}

int main(){
    p[0]=1;
    for(int i=1;i<MAXN;++i) p[i]=MUL(BASE, p[i-1]);
    int tcc;
    scanf("%d", &tcc);
    for(int tc=0;tc<tcc;++tc){
        scanf("%s", str);
        n=strlen(str);
        int ls=0,rs=n-1, le=1, re=n;
        int lh=str[0]-'a'+1, rh=str[n-1]-'a'+1;
        int sol=0;
        while(ls<=rs){
            while(lh!=rh){
                lh=ADD(MUL(lh, BASE), str[le]-'a'+1);
                ++le;
                --rs;
                rh=ADD(MUL(str[rs]-'a'+1, p[re-rs-1]), rh);
            }
            if(ls==rs && le==re){
                sol++;
                break;
            }else{
                sol+=2;
            }
            ls=le;le=ls+1;lh=str[ls]-'a'+1;
            re=rs;rs=re-1;rh=str[rs]-'a'+1;
        }
        printf("%d\n", sol);
    }
}

Compilation message (stderr)

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

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