제출 #1332525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1332525		Warinchai	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	0 ms	344 KiB

palindromic

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

int md=1e9+7;
int val[1000005];
int sum[1000005];
int pw[10000005];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;cin>>t;
    pw[0]=1;
    while(t--){
        string s;cin>>s;
        int n=s.size();
        for(int i=1;i<=n;i++)pw[i]=(pw[i-1]*26)%md;
        for(int i=1;i<=n;i++){
            val[i]=s[i-1]-'a';
            sum[i]=(sum[i-1]*26+(s[i-1]-'a'))%md;
        }
        int st=1,en=n;
        int l=0;
        int ans=0;
        int pre=0,suf=0;
        while(st<=en){
            pre=(pre*26+val[st]);
            suf=(val[en]*pw[l]+suf);
            if(st==en){
                if(pre==suf)ans++;
                break;
            }
            st++,en--,l++;
            if(pre==suf){
                l=pre=suf=0;
                ans+=2;
            }
        }
        if(l>0)ans++;
        cout<<ans<<"\n";
    }
}

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