Submission #585593

#	Time	Username	Problem	Language	Result	Execution time	Memory
585593		tengiz05	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	226 ms	12780 KiB

palindromic

#include <bits/stdc++.h>

using i64 = long long;
using namespace std;

struct Hash {
    static constexpr int P = 1000000007, M = 29;
    int n;
    std::vector<int> a, pw;
    Hash(std::string s) : n(s.size()), a(n + 1), pw(n + 1, 1) {
        for (int i = 1; i <= n; i++)
            pw[i] = 1LL * pw[i - 1] * M % P;
        for (int i = 0; i < n; i++)
            a[i + 1] = (1LL * a[i] * M + (s[i] - 'a' + 1)) % P;
    }
    int get(int l, int r) {
        r++;
        int res = a[r] - 1LL * pw[r - l] * a[l] % P;
        if (res < 0)
            res += P;
        return res;
    }
};

void solve() {
    string s;
    cin >> s;
    
    int n = s.size();
    
    int ans = 0;
    
    int l = 0, r = n - 1;
    
    Hash h(s);
    
    for (int i = 0; i < n / 2; i++) {
        if (h.get(l, i) == h.get(n - i - 1, r)) {
            ans += 2;
            l = i + 1;
            r = n - i - 2;
        }
    }
    
    ans += l <= r;
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    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