Submission #917779

#	Time	Username	Problem	Language	Result	Execution time	Memory
917779		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	579 ms	17116 KiB

palindromic

#pragma GCC optimize("03")
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define ln '\n'
#define F first 
#define S second
#define pb push_back
#define ins insert
#define all(v) v.begin(), v.end()
#define whole(a, n) a + 1, a + n + 1
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int sz = 1e6 + 5;
const int inf = 1e9 + 7;
string s;
int n, sh[sz];
void get_hash(){
    int h = 0, pw = 1, p = 47;
    for(int i = 1; i <= n; i++){
        h = (h + 1LL * (s[i] - 'a' + 1) * pw % inf) % inf;
        pw = 1ll * pw * p % inf;
        sh[i] = h;
    }
}
int bin_pow(int x, int y){
    int res = 1;
    while(y){
        if(y & 1){
            res = 1LL * res * x % inf;
        }
        x = 1LL * x * x % inf;
        y >>= 1;
    }
    return res;
}
bool check(int l, int r){
    l--;
    int h1 = (sh[r] - sh[l] + inf) % inf;
    int h2 = (sh[n-l] - sh[n-r] + inf) % inf;
    /// cout << h1 << " " << h2 << " ";
    if(1LL * h1 * bin_pow(47, (n - r - l)) % inf == h2) return true;
    return false;
}
void solve(){
    cin >> s;
    n = s.length();
    s = '.' + s;
    get_hash();
    int ans = 0;
    int m = n / 2 + n % 2;
    for(int i = 1; i <= m; i++){
        bool t = false;
        for(int j = i; j <= m; j++){
            if(check(i, j)){
                ans += 2;
                i = j;
                t = true;
                if(i == j and i == m and n % 2) ans--;
                break;
            }
        }
        if(!t){
            ans++;
            break;
        }
    }
    cout << ans << ln;
   /*
    for(int i = 1; i <= n; i++) cout << sh[i] << " ";
    cout << ln;
    cout << check(2, 2) << ln;
    cout << bin_pow(47, 4);
    */
}
signed main(){
    fastio
    int T = 1;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

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