Submission #977671

#	Time	Username	Problem	Language	Result	Execution time	Memory
977671		berr	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	84 ms	19632 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+29;
const int mod = 1e9+7;
 
 
int mul(int x, int y){
    x*=y;
    x-=(x/mod)*mod;
    return x;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t; cin >> t;
    vector<int> p(1e6+38);
    p[0] = 1;
    for(int i=1; i<=1e6; i++){
        p[i] = mul(p[i-1], 29);
    }
 
 
    while(t--){
        string s; cin >> s;
        int n = s.size();
        int sum=0, ans=0;
        vector<int> va(n);

        for(int i=0; i<n; i++){
            sum+=mul((s[i]-'a'+1),p[i+1]);
            if(sum>=mod) sum-=mod;
            va[i]=sum;
        }
 
        int s2=0, l=0, plast=n;
        int siz=0;
        for(int i=n-1; i>=n/2; i--){
            s2=mul(s2, 29);
            s2+=mul((s[i]-'a'+1), 29);
            if(s2>=mod) s2-=mod;
            int val= (l+ mul(s2, p[n-plast]));
            if(val>=mod) val-=mod;

            if(val==va[n-i-1]){
                ans+=2; 
                siz+=(plast-i)*2;
                if(siz>n) ans--, siz-=(plast-i);
                l=val;
                s2=0;
                plast=i;
            }
        }
 
        if(siz!=n) ans++;
        cout<<ans<<"\n";
    }
}

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