Submission #1118276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118276		Icelast	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	92 ms	40288 KiB

palindromic

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 5*1e5+5, INF = 1e9+9, mod = 1e9+9, base = 101;
int N = 2e6;
vector<ll> bp(N+1, 1);
void calc(){
    for(int i = 1; i <= N; i++){
        bp[i] = bp[i-1]*base%mod;
    }
}
void solve(){
    string s;
    cin >> s;
    int n = s.size();
    s = ' ' + s;
    vector<ll> hsh(n+1, 0);
    for(int i = 1; i <= n; i++){
        hsh[i] = hsh[i-1]+(s[i]-'a'+1)*bp[i-1];
    }
    auto get_hash = [&](int l, int r) -> ll{
        ll raw = (hsh[r]-hsh[l-1]+mod)%mod;
        return raw*bp[N-l]%mod;
    };
    vector<int> f(n+1, -INF);
    f[0] = 0;
    int ans = 1;
    int L = 1, R = n;
    for(int i = 1; i <= n/2; i++){
        if(get_hash(L, i) == get_hash(n-i+1, R)){
            f[i] = f[L-1]+2;
            L = i+1;
            R = n-i+1-1;
        }
        if(i == n/2 && n%2==0){
            ans = max(ans, f[i]);
        }else{
            ans = max(ans, f[i]+1);
        }
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    calc();
    int t;
    cin >> t;
    while(t--){
        solve();
        cout << "\n";
    }
    return 0;
}

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