Submission #852205

#	Time	Username	Problem	Language	Result	Execution time	Memory
852205		c2zi6	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	365 ms	25492 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

vector<ll> Bpow;
ll B = 31;
ll P = 1e9 + 9;

struct HASHED {
    vector<ll> pref;
    HASHED(string s) {
        if (Bpow.empty()) Bpow.push_back(1);
        while (Bpow.size() <= s.size()) Bpow.push_back(Bpow.back() * B % P);
        pref = vector<ll>(s.size()+1);
        pref[0] = 0;
        for (int i = 1; i <= s.size(); i++) {
            pref[i] = (pref[i-1] * B + (s[i-1] - 'a' + 1)) % P;
        }
    }
    ll subst(ll l, ll r) {
        ll a = pref[l] * Bpow[r-l+1] % P;
        ll b = pref[r+1];
        return (b + P - a) % P;
    }
};

void solve() {
    string s;
    cin >> s;
    int n = s.size()/2;
    string a, b;
    for (int i = 0; i < n; i++) {
        a.push_back(s[i]);
        b.push_back(s[i+n+s.size()%2]);
    }
    HASHED A(a), B(b);
    // while (true) {
    //     int t, l, r;
    //     cin >> t >> l >> r;
    //     if (t == 1) cout << A.subst(l-1, r-1) << endl;
    //     else cout << B.subst(l-1, r-1) << endl;
    // }
    int l = 0, r = 0;

    int ans = 0;
    while (true) {
        if (r == n) {
            cout << ans + s.size()%2 << endl;
            return;
        }
        while (A.subst(l, r) != B.subst(n-r-1, n-l-1)) {
            r++;
            if (r == n) {
                cout << ans + 1 << endl;
                return;
            }
        }

        l = r+1;
        r = r+1;

        ans += 2;
    }
}

int main() {
    int t = 1;
    cin >> t;
    while (t--) solve();
}

Compilation message (stderr)

palindromic.cpp: In constructor 'HASHED::HASHED(std::string)':
palindromic.cpp:18:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for (int i = 1; i <= s.size(); i++) {
      |                         ~~^~~~~~~~~~~

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