Submission #168207

#	Time	Username	Problem	Language	Result	Execution time	Memory
168207		mhy908	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	480 ms	11136 KiB

palindromic

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL mod=1000000007;
int t;
char str[1000010];
LL power(LL a, LL b){
    if(!b)return 1;
    LL ret=power(a, b/2);
    return b%2?ret*ret%mod*a%mod:ret*ret%mod;
}
int main()
{
    scanf("%d", &t);
    for(int u=1; u<=t; u++){
        memset(str, 0, sizeof(str));
        scanf("%s", str+1);
        int ans=0;
        int re=strlen(str+1), fr=1;
        bool ch=true;
        while(1){
            LL hash1=0, hash2=0;
            for(int i=0; fr+i<re-i; i++){
                hash1*=997;
                hash1+=(LL)(str[fr+i]-'a'+1);
                hash1%=mod;
                hash2+=(LL)(str[re-i]-'a'+1)*power(997LL, (LL)i);
                hash2%=mod;
                if(hash1==hash2){
                    bool flag=true;
                    for(int j=0; j<=i; j++){
                        if(str[fr+j]!=str[re-i+j]){
                            flag=false;
                            break;
                        }
                    }
                    if(flag){
                        fr+=i+1;
                        re-=i+1;
                        ans+=2;
                        if(fr-1==re)ch=false;
                        break;
                    }
                }
                if(fr+i+1>=re-i-1){
                    fr+=i+1;
                    re-=i+1;
                }
            }
            if(fr>=re&&ch){
                ans++;
                break;
            }
            if(fr>=re)break;
        }
        printf("%d\n", ans);
    }
}

Compilation message (stderr)

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

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