Submission #224100

#	Time	Username	Problem	Language	Result	Execution time	Memory
224100		SorahISA	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	535 ms	20780 KiB

palindromic

#pragma GCC optimize ("Ofast", "unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define double long double
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;
 
#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0)
 
const int mod = 1E9 + 9;
const int p = 1000;
 
void solve() {
    int n;
    string s;
    cin >> s, n = s.size();
    
    if (n == 1) {cout << 1 << "\n"; return;}
    
    int Hash[n];
    for (int i = 0; i < n; ++i) Hash[i] = ((i ? Hash[i-1] : 0) * p + s[i]) % mod;
    
    auto fastpow = [](int base, int pow, int ans = 1) {
        while (pow) {
            if (pow & 1) ans = ans * base % mod;
            base = base * base % mod, pow >>= 1;
        }
        return ans;
    };
    
    auto getHash = [&](int L, int len) {
        return (Hash[L+len-1] - (L ? Hash[L-1] * fastpow(p, len) % mod : 0) + mod) % mod;
    };
    
    // for (int i = 0; i < n; ++i) cerr << getHash(i, 1) << " \n"[i == n-1];
    
    int tok = 0, ans = 0;
    for (int i = 0; i < n/2; ++i) {
        if (getHash(tok, i-tok+1) == getHash(n-i-1, i-tok+1)) {
            ans += 2;
            tok = i + 1;
            if (n%2 and i == n/2-1) ++ans;
        }
        else if (i == n/2-1) ++ans;
    }
    
    cout << ans << "\n";
}
 
int32_t main() {
    fastIO();
    
    int t;
    cin >> t;
    while (t--) solve();
    
    return 0;
}

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