Submission #1221563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221563		yassia	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	115 ms	12032 KiB

palindromic

#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;

const ll INF = 1e18;
const ll mod = 1e9+9;
ll p = 31;

ll add(ll a, ll b){
    return ((a%mod)+(b%mod))%mod;
}
ll mult(ll a, ll b){
    return ((a%mod)*(b%mod))%mod;
}
ll sub(ll a, ll b){
    return add(a, mod-(b%mod));
}
ll ord(char s){
    return ((s-'a')+1);
}
void solve() {
    string s;
    cin >> s;
    ll n = (ll)s.size();
    vector<ll> pows(n+1);
    pows[0] = 1;
    for (ll i =1; i <= n; i++){
        pows[i] = mult(pows[i-1],p);
    }
    deque<char> o;
    for (auto x : s) {
        o.emplace_back(x);
    }
    ll s1 = 0;
    ll s2 = 0;
    ll len1 = 0;
    ll len2= 0;
    ll ans = 0;
    while(!o.empty()){
        if (o.size()==1) {
            if(s1 == s2 && s1 != 0) {
                ans += 3;
            }
            else {
                ans += 1;
            }
            break;
        }
        char s0 = o.front();
        char sn = o.back();
        s1 = add(s1, mult(ord(s0),pows[len1]));
        s2 = add(ord(sn),mult(s2, p));
        len1++;
        len2++;
        o.pop_front();
        o.pop_back();
        if (s1 == s2) {
            ans += 2;
            s1 = 0;
            s2 = 0;
            len1 = 0;
            len2 = 0;
        }
        else if (o.empty()){
            ans += 1;
        }
    }
    cout<<ans<<endl;

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ll t;
    cin>>t;
    while(t--) solve();
#ifdef local
    printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC);
#endif
}

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