Submission #62658

#	Time	Username	Problem	Language	Result	Execution time	Memory
62658		Nnandi	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	99 ms	32144 KiB

palindromic

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

typedef long long ll;
const ll mod = 1000000009LL;
const ll prm = 103LL;
vector<int> sol;

int Get_Max_Partition(string &s, int l, int r) {
    if(l > r) return 0;
    if(l == r) return 1;
    if(s[l] == s[r]) return 2+ Get_Max_Partition(s,l+1,r-1);
    ll exp1 = s[l];
    ll exp2 = s[r];
    ll pow = 1LL;
    for(int i=1;i<(r-l+1)/2;i++) {
        pow *= prm;
        pow = pow % mod;
        exp1 = exp1 * prm + s[l+i];
        exp1 = exp1 % mod;
        exp2 = exp2 + pow * s[r-i];
        exp2 = exp2 % mod;
        if(exp1 == exp2) {
            bool match = true;
            for(int j=0;j<=i && match;j++) {
                if(s[l+j] != s[r-i+j]) match = false;
            }
            if(match) {
                return 2 + Get_Max_Partition(s,l+i+1,r-i-1);
            }
        }
    }
    return 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test;
    cin>>test;
    for(int tc=0;tc<test;tc++) {
        string s;
        cin>>s;
        sol.push_back(Get_Max_Partition(s,0,s.size()-1));
    }
    for(int d:sol) {
        cout<<d<<endl;
    }
    return 0;
}

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