Submission #1217294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217294		kiennguyendinh	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	131 ms	17124 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
int t;
string s;
long long h[1000001];
vector<char> res;
long long base = 31,mod = 1000000007;
long long exp0[1000001];
int siz;
long long getHash(int l,int r){
    long long re;
    if(l == 0) re = h[r];
    else re = (h[r] - h[l - 1] + mod) % mod;
    re = (re * exp0[1000000 - l])%mod;
    return re;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("censor.in","r",stdin);
    //freopen("censor.out","w",stdout);
    exp0[0] = 1;
    for(int i = 1;i <= 1000000;i++) exp0[i] = (exp0[i - 1] * base) % mod;
    cin >> t;
    while(t--){
        int res = 0;
        cin >> s;
        //cout << s << "\n";
        h[0] = (int) s[0] - 'a' + 1;
        siz = s.size();
        for(int i = 1;i < siz;i++){
            h[i] = (h[i - 1] + ((int) s[i] - 'a' + 1)*exp0[i])%mod;
        }
        int l = 0,r = siz - 1,lastL = 0,lastR = siz - 1;
        bool en = false;
        while(l <= r){
            if(getHash(lastL,l) == getHash(r,lastR)){
                //cout << lastL << " " << l << " " << r << " " << lastR << "\n";
                if(l == r) res++;
                else res += 2;
                lastL = l + 1;
                lastR = r - 1;
                if(lastL > lastR){
                    en = true;
                }
            }
            l++;
            r--;
        }
        if(!en) res++;
        cout << res << "\n";
    }
    return 0;
}

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