Submission #1226085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226085		putuputu	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	156 ms	18984 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int b=911;
int ph[N];
int p[N];

void h(string s){
    int n=s.size();
    ph[0]=s[0];
    for(int i=1; i<n; i++){
        ph[i]=ph[i-1]*b+s[i];
    }
}
int get(int l, int r){
    if(l==0){
        return ph[r];
    }else{
        return ph[r]-ph[l-1]*p[r-l+1];
    }
}
signed main(){
    int t;
    cin >> t;
    p[0]=1;
    for(int i=1; i<N; i++){
        p[i]=p[i-1]*b;
    }
    while(t--){
        int ans=0;
        string s;
        cin >> s;
        int n=s.size();
        int l=0, r=n-1;
        h(s);
        while(l<r){
            bool g=false;
            for(int i=1; l+i-1<r-i+1; i++){
                if(get(l, l+i-1)==get(r-i+1, r)){
                    ans+=2;
                    l+=i;
                    r-=i;
                    g=true;
                    break;
                }
                // if(l!=r){
                //     ans++;
                // }
            }
            if(g==false){
                break;
            }
        }
        if(l<=r){
            ans++;
        }
        cout << ans << endl;
    }
}

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