Submission #462455

#	Time	Username	Problem	Language	Result	Execution time	Memory
462455		JovanB	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	271 ms	20584 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int MOD = 1000000007;
const int p = 41;
 
int hsh[1000005];
int powers[1000005];
 
int add(int a, int b){
    return (a+b)%MOD;
}
 
int mul(int a, int b){
    return ((ll)a*b)%MOD;    
}
 
int substring_hash(int l, int r){
    if(l == 0) return hsh[r];
    return add(hsh[r], mul(powers[r-l+1], MOD - hsh[l-1]));
}
 
void solve(){
    string s;
    cin >> s;
    int n = s.size();
    if(n == 1){
        cout << 1 << "\n";
        return;
    }
    powers[0] = 1;
    for(int i=1; i<=n; i++) powers[i] = mul(p, powers[i-1]);
    hsh[0] = 1 + (s[0] - 'a');
    for(int i=1; i<n; i++){
        hsh[i] = add(mul(p, hsh[i-1]), (s[i]-'a') + 1);
    }
    int l1=0, r1=0, l2=n-1, r2=n-1;
    int res = 0;
    while(1){
        //cout << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
        //cout << substring_hash(l1, r1) << " " << substring_hash(l2, r2) << endl;
        if(substring_hash(l1, r1) == substring_hash(l2, r2)){
            res += 2;
            r2 = l2-1;
            l1 = r1+1;
            r1++;
            l2--;
            if(r1 > l2){
                cout << res << "\n";
                return;
            }
            if(r1 == l2){
                cout << res+1 << "\n";
                return;
            }
        }
        else{
            r1++;
            l2--;
            if(r1 >= l2){
                cout << res+1 << "\n";
                return;
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout << fixed;
    
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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