Submission #125323

#	Time	Username	Problem	Language	Result	Execution time	Memory
125323		semiauto	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	628 ms	11228 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
const long long p1=997,r1=1000000007,p2=1439,r2=1000000009;
long long t,ans;
string s;
void solve(long long l,long long r) {
    long long h1=0,h2=0,h3=0,h4=0,s1=1,s2=1;
    while (h1!=h2 || h3!=h4 || !h1) {
        if (l>=r) {
            ans++;
            return;
        }
        s1=(s1*p1)%r1;
        s2=(s2*p2)%r2;
        h1=(h1+s1*(s[l]-'a'+1))%r1;
        h3=(h3+s2*(s[l]-'a'+1))%r2;
        h2=((h2+(s[r]-'a'+1))*p1)%r1;
        h4=((h4+(s[r]-'a'+1))*p2)%r2;
        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