Submission #915837

#	Time	Username	Problem	Language	Result	Execution time	Memory
915837		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	304 ms	20120 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 1e6 + 5;
const int P = 43;
const int M = 1e9 + 7;

int n;
int p[N], h[N];

bool check_equal(int a, int b, int l) {
    int ha = (h[a + l - 1] - h[a - 1] + M) % M;
    int hb = (h[b + l - 1] - h[b - 1] + M) % M;
    return 1ll * ha * p[b - a] % M == hb;
}

int main() {
    int Q; cin >> Q;
    while(Q--){
        string s;
        cin >> s;
        n = s.size();

        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            p[i] = 1ll * p[i - 1] * P % M;
        }

        h[0] = 0;
        for (int i = 1; i <= n; i++) {
            h[i] = (h[i - 1] + 1LL * (s[i - 1] - 'a' + 1) * p[i - 1] % M) % M;
        }
        int p1 = 0, p2 = n - 1;
        ll ans = 0;
        while(p1 <= p2){
            bool ok = false;
            for(int k = 1; 2 * k <= p2 - p1 + 1; k++){
                if(check_equal(p1 + 1, p2 - k + 2, k)){
                    p1 += k;
                    p2 -= k;
                    ans += 2;
                    ok = true;
                    break;
                }
            }
            if(!ok){
                ans++;
                break;
            }
        }
        cout << ans << '\n';
    }
}

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