제출 #97287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97287		dalgerok	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	176 ms	28940 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;


const int N = 1e6 + 5, MOD1 = 1e9 + 1337, MOD2 = 999888777;



string s;
int n, p1[N], p2[N], h1[N], h2[N];

inline pair < int, int > get_hash(int l, int r){
    int cur1 = 1LL * (h1[r] - h1[l - 1] + MOD1) % MOD1 * p1[N - r] % MOD1,
        cur2 = 1LL * (h2[r] - h2[l - 1] + MOD2) % MOD2 * p2[N - r] % MOD2;
    return make_pair(cur1, cur2);
}

inline void solve(){
    cin >> s;
    n = (int)s.size();
    s = '#' + s;
    for(int i = 1; i <= n; i++){
        h1[i] = (h1[i - 1] + 1LL * (s[i] - 'a' + 1) * p1[i] % MOD1) % MOD1;
        h2[i] = (h2[i - 1] + 1LL * (s[i] - 'a' + 1) * p2[i] % MOD2) % MOD2;
    }
    int l = 1, r = n, ans = 0;
    while(l <= r){
        for(int len = 1; l + len - 1 < r - len + 1; len++){
            if(get_hash(l, l + len - 1) == get_hash(r - len + 1, r)){
                ans += 2;
                l += len;
                r -= len;
                goto to;
            }
        }
        ans += 1;
        break;
        to:;
    }
    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    p1[0] = p2[0] = 1;
    for(int i = 1; i < N; i++){
        p1[i] = 1LL * p1[i - 1] * 59 % MOD1;
        p2[i] = 1LL * p2[i - 1] * 45 % MOD2;
    }
    int test;
    cin >> test;
    while(test--){
        solve();
    }
}

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