Submission #1193805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193805		tin_le	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	86 ms	18964 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    const ull B = 1315423911ULL;
    while(T--){
        string s;
        cin >> s;
        int n = s.size();
        vector<ull> h(n+1,0), p(n+1,1);
        for(int i=0;i<n;++i){
            h[i+1] = h[i]*B + (unsigned char)s[i];
            p[i+1] = p[i]*B;
        }
        auto get = [&](int l, int r){
            return h[r+1] - h[l]*p[r-l+1];
        };

        int i = 0, j = n-1, cnt = 0;
        while(i <= j){
            int L = j - i + 1, half = L/2;
            bool ok = false;
            for(int l = 1; l <= half; ++l){
                if(get(i, i+l-1) == get(j-l+1, j)){
                    i += l;
                    j -= l;
                    cnt += 2;
                    ok = true;
                    break;
                }
            }
            if(!ok){
                if(i <= j) ++cnt;
                break;
            }
        }
        cout << cnt << "\n";
    }
    return 0;
}

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