Submission #125324

#	Time	Username	Problem	Language	Result	Execution time	Memory
125324		semiauto	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	595 ms	3296 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
const long long p1=997,r1=1000000007;
long long t,ans;
string s;
void solve(long long l,long long r) {
    long long h1=0,h2=0,s1=1;
    while (h1!=h2 || !h1) {
        if (l>=r) {
            ans++;
            return;
        }
        s1=(s1*p1)%r1;
        h1=(h1+s1*(s[l]-'a'+1))%r1;
        h2=((h2+(s[r]-'a'+1))*p1)%r1;
        l++;r--;
    }
    ans+=2;
    if (l<=r)
        solve(l,r);
}
int main() {
    cin>>t;
    while (cin>>s) {
        ans=0;
        solve(0,s.length()-1);
        cout<<ans<<endl;
    }
}

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