Submission #256284

#	Time	Username	Problem	Language	Result	Execution time	Memory
256284		giorgikob	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	245 ms	26492 KiB

palindromic

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e6 + 5;
const int p = 31, mod = 1e9 + 9;

inline void test_case(){

        string s;
        cin >> s;
        s = '#' + s;
        int n = s.size();
        vector<ll>hash_val(n+1,0), P(n+5,0);

        int answer = 0;

        P[0] = 1;
        for(int i = 1; i <= n; i++){
                P[i] = P[i-1] * p;
                P[i] %= mod;
        }

        for(int i = 1; i < n; i++){
                hash_val[i] = hash_val[i-1] + (s[i] - 'a' + 1) * P[i-1];
                hash_val[i] %= mod;
        }

        //hash_val[n] = hash_val[n-1];

        int l = 1, r = 1;
        int sl = n-1, sr = n-1;

        while(r < sl){
                if( ( (hash_val[r] - hash_val[l-1] + mod) * P[sl-l] ) % mod  == (hash_val[sr] - hash_val[sl-1] + mod) % mod ){
                        //cout << r << endl;
                        r++;
                        l = r;
                        sl--;
                        sr = sl;
                        answer += 2;
                } else {
                        r++;
                        sl--;
                }
        }

        if(l <= n/2) answer ++;

        cout << answer << endl;
}

int main(){

        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

        int T;
        cin >> T;
        while(T--){
                test_case();
        }
}

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