Submission #1279652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279652		nanaseyuzuki	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	112 ms	19696 KiB

palindromic

#include <bits/stdc++.h>
/*
    --> Author: Kazuki_Hoshino__8703 <--  
    I love Megumi Katou ☆*: .｡. o(≧▽≦)o .｡.:*☆
*/
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) sort(a.begin(), a.end());
#define unique(a) a.erase(unique(a.begin(), a.end()), a.end());
using namespace std;

const int mn = 1e6 + 5, mod = 1e9 + 7, base = 311;

string s;
int h[mn], mu[mn];

int get(int l, int r){
    return ((h[r] - h[l - 1] * mu[r - l + 1]) % mod + mod) % mod;
}

void solve(){
    cin >> s;
    mu[0] = 1;
    int n = s.size(); s = "#" + s;
    for(int i = 1; i <= n; i++){
        mu[i] = (mu[i - 1] * base) % mod;
        h[i] = ((h[i - 1] * base) % mod + s[i] - 'a' + 1) % mod;
    }
    int l = 1, ptr = 1, res = 0;
    while(l <= n / 2 && ptr <= n / 2){
        if(get(l, ptr) == get(n - ptr + 1, n - l + 1)){
            l = ptr + 1;
            ptr ++;
            res += 2;
        }
        else{
            ptr ++;
        }
    }
    if(l <= (n + 1) / 2) res ++;
    cout << res << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}

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