Submission #1166404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166404		VMaksimoski008	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	203 ms	19976 KiB

palindromic

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

struct H {
    int n;
    string s;
    const ll p = 31;
    vector<ll> pw, hash;

    H(string _s) : s(_s) {
        n = s.size() - 1;
        pw.resize(n+1);
        hash.resize(n+1);

        pw[0] = 1;
        for(int i=1; i<=n; i++) pw[i] = (pw[i-1] * p) % mod;

        for(int i=1; i<=n; i++)
            hash[i] = (hash[i-1] + pw[i] * (s[i] - 'a')) % mod;
    }

    ll get_hash(int l, int r) {
        return (hash[r] - hash[l-1] + mod) % mod;
    }

    bool same(int l1, int r1, int l2, int r2) {
        if(r2 - l2 != r1 - l1) return 0;
        return (get_hash(l1, r1) * pw[l2-l1]) % mod == get_hash(l2, r2);
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int q; cin >> q;
    while(q--) {
        string s; cin >> s;
        int n = s.size(), ans = 0;
        s = "." + s;

        H hash(s);
        int l=1, r=n;
        while(l < r) {
            bool ok = 0;
            int l2=l, r2=r;
            while(l2 < r2) {
                if(hash.same(l, l2, r2, r)) {
                    ok = 1;
                    ans += 2;
                    break;
                }

                l2++;
                r2--;
            }

            if(ok) {
                l = l2 + 1;
                r = r2 - 1;
            } else {
                ans++;
                break;
            }
        }
        cout << ans + (l == r) << '\n';
    }
}

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