Submission #1116573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116573		PagodePaiva	Palindromic Partitions (CEOI17_palindromic)	C++17	60 / 100	1099 ms	16612 KiB

palindromic

#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second

using namespace std;

const int N = 100010;
const int p = 1e9+7;
const int q = 1e9+9;
const int b = 127;
int pot[N][2];
int potinv[N][2];

int binpow(int a, int b, int mod){
    if(b == 0) return 1;
    int t = binpow(a, b/2, mod);
    t *= t;
    t %= mod;
    if(b%2 == 0) return t;
    else return (a*t)%mod;
}

struct hs{
    pair <int, int> pref[N];
    void build(string s){
        pref[0] = {0, 0};
        for(int i = 0;i < s.size();i++){
            pref[i+1].fr = (pref[i].fr + ((s[i]-'a'+1)*pot[i][0])%p)%p;
            pref[i+1].sc = (pref[i].sc+((s[i]-'a'+1)*pot[i][1])%q)%q;
        }
    }
    pair <int, int> query(int l, int r){
        l++;
        r++;
        return {(((pref[r].first+p-pref[l-1].first)%p)*potinv[l-1][0])%p, (((pref[r].second+q-pref[l-1].second)%q)*potinv[l-1][1])%q};
    }
    bool get(int l1, int r1, int l2, int r2){
        if(query(l1, r1) == query(l2, r2)) return true;
        return false;
    }
} h;
int res[N];

void solve(){
    string s;
    cin >> s;
    h.build(s);
    int n = s.size();
    if(n == 1){
        cout << 1 << '\n';
        return;
    }
    int st = (n%2 == 0 ? (n-1)/2 : n/2);
    res[st+1] = 0;
    res[st] = (n%2 == 1 ? 1 : (s[st] == s[st+1] ? 2 : 1));
    for(int i = st-1;i >= 0;i--){
        int r = (n%2 == 1 ? st+st-i : st+st-i+1);
        //cout << i << ' ' << r << '\n';
        res[i] = 1;
        for(int j = i;j <= st;j++){
          //  cout << i << ' ' << j << ' ' << r-(j-i) << ' ' << r << ' ' << h.get(i, j, r-(j-i), r) << '\n';
            if(h.get(i, j, r-(j-i), r)){
                res[i] = max(res[i], res[j+1]+2);
            }
        }
    }
    cout << res[0] << '\n';
}

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int t;
    cin >> t;
    pot[0][0] = pot[0][1] = 1;
    potinv[0][0] = potinv[0][1] = 1;
    for(int i = 1;i < N;i++){
        pot[i][0] = (pot[i-1][0]*b)%p;
        pot[i][1] = (pot[i-1][1]*b)%q;
        potinv[i][0] = binpow(pot[i][0], p-2, p);
        potinv[i][1] = binpow(pot[i][1], q-2, q);
    }
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

palindromic.cpp: In member function 'void hs::build(std::string)':
palindromic.cpp:28:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i = 0;i < s.size();i++){
      |                       ~~^~~~~~~~~~

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