Submission #1165540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165540		hassanfathi2002	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	0 ms	320 KiB

palindromic

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

const int mod = 1e9 + 7;

struct Hash{
    vector<int> p = {31 , 43 , 47};
    int n , m = p.size();
    vector<vector<ll>> pw, inv, pre;
    vector<ll> ip;

    Hash(const string &s){
        n = s.size();
        pw.resize(m);
        inv.resize(m);
        pre.resize(m);
        ip.resize(m);

        for(auto &a : pw)
            a.resize(n + 1);
        for(auto &a : pre)
            a.resize(n + 1);
        for(auto &a : inv)
            a.resize(n + 1);

        for(int i = 0; i < m; i ++){
            pw[i][0] = inv[i][0] = 1;
            ip[i] = mod_inv(p[i]);
        }
        for(int i = 0; i < m; i ++){
            for (int j = 1; j <= n; j ++){
                pw[i][j] = pw[i][j - 1] * p[i] % mod;
                inv[i][j] = inv[i][j - 1] * ip[i] % mod;
            }
        }
        int n = s.size();
        for(int i = 0; i < m; i ++){
            for (int j = 1; j <= n; j ++){
                pre[i][j] = (pre[i][j - 1] + (ll) (s[j - 1] - 'a' + 1) * pw[i][j]) % mod;
            }
        }
    }

    ll power(ll a , ll b){
        a %= mod;
        ll ret = 1;
        while(b){
            if(b & 1) 
                ret = (ret * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return ret;
    } 

    ll mod_inv(ll a){ // power(a , tot[b] - 1)
        return power(a , mod - 2);
    }

    vector<int> get(int l , int r){ // 0 based
        l ++ , r ++;
        vector<int> ret(m);
        for(int i = 0; i < m; i ++){
            ret[i] = (pre[i][r] - pre[i][l - 1] + mod) * inv[i][l] % mod;
        }
        return ret;
    }
};

void hassan(){
    string s;
    cin >> s;
    int n = s.size();
    Hash H(s);

    int res = 0;
    int l = 0;
    for(int r = 0; r < n / 2; r ++){
        // cout << l + 1 << " " << r + 1 << " " << n - r << " " << n - l << '\n';        
        if(H.get(l , r) == H.get(n - 1 - r, n - 1 - l)){
            l = r + 1;
            res += 2;
        }
        // cout << l + 1 << " " << r + 1 << " " << res << '\n';
    }
    res += l != n / 2 + 1;
    cout << res << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin >> t; while(t --)
    hassan();
}

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