Submission #1316211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316211		michud07	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	53 ms	17172 KiB

palindromic

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

const ll p[2] = {29, 31}, m[2] = {1'000'000'007, 1'000'000'009};
const int N = 1e6 + 4;
string s;
ll powers[2][N];

void precompute(bool b = 0){
    powers[b][0] = 1;
    for(int i = 1 ; i < N ; i++){
        powers[b][i] = (powers[b][i - 1] * p[b]) % m[b];
    }
    if(!b) precompute(!b);
}

int solve(){
    int n = s.size(), len = 0, ans = 0;
    pair<ll, ll> h1 = {0, 0}, h2 = {0, 0};
    for(int i = 0 ; i < n / 2 ; i++){
        int l1 = s[i] - 'a', l2 = s[n - i - 1] - 'a';
        h1.first = (h1.first + l1 * powers[0][len]) % m[0];
        h1.second = (h1.second + l1 * powers[1][len]) % m[1];
        h2.first = (h2.first * p[0] + l2) % m[0];
        h2.second = (h2.second * p[1] + l2) % m[1];
        len++;
        if(h1 == h2){
            ans += 2;
            len = 0;
            h1 = {0, 0};
            h2 = {0, 0};
        }
    }
    if(!(n % 2) && h1 == h2) return ans;
    return ans + 1;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int t;
    cin >> t;
    precompute();
    while(t--){
        cin >> s;
        cout << solve() << '\n';
    }
}

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