Submission #972621

#	Time	Username	Problem	Language	Result	Execution time	Memory
972621		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	7 ms	17500 KiB

palindromic

#pragma GCC optimize ("Ofast")

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define Abdoo ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

void pr(vector<int> v) {
    for (int i = 0; i < v.size(); ++i) {
        cout << v[i] << " ";
    }
    cout << "\n";
}
const int N = 1e6 +5, MOD = 1e9 + 9;

ll pw[N], inv[N], pref[N], p = 31;
ll add(ll a,ll b){
    return (a+b) % MOD;
}
ll mul(ll a,ll b){
    return 1ll * (a * b)%MOD;
}
ll sub(ll a, ll b){
    return ((a-b) % MOD + MOD) % MOD;
}

ll fast_power(ll b, ll p){
    ll ans = 1;
    while(p){
        if(p&1) ans = mul(ans, b);
        b = mul(b, b);
        p /= 2;
    }
    return ans;
}

void pre(){
	pw[0] = inv[0] = 1;
	ll inverse = fast_power(p, MOD - 2);
	for(int i = 1; i < N; i++){
		pw[i] = mul(pw[i-1] , p);
		inv[i] = mul(inv[i-1], inverse);
	}
}
ll getHash(int l, int r){
	l++,r++;
    return mul(add(pref[r],MOD - pref[l-1]), inv[l-1]);
}

void generateHash(string &s){
    for (int i = 1; i <= (int)s.size(); ++i) {
        int idx = s[i-1]-'a'+1;
        pref[i] = mul(idx, pw[i-1]);
        pref[i] = add(pref[i],pref[i-1]);
    }
}


int main() {
    Abdoo
	pre();
    int tc = 1;
    cin >> tc;
    while (tc--) {
        string s;
        cin >> s;
        generateHash(s);
        int st = 0, en = s.size()- 1, ans = 0;
        while(st < en){
        	int st2 = st, en2 = en;
        	while(st2 < en2 && getHash(st, st2) != getHash(en2, en)){
        		st2++, en2--;
        	}
        	if(st2 < en2 &&getHash(st, st2) == getHash(en2, en)){
        		//cout << st << " " << st2 << " " << en2 << " " << en << "\n";
        		ans += 2;
        	}
        	st = st2, en = en2;
        	st++, en--;
        }
        ans++;
        cout << ans << "\n";
    }
    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'void pr(std::vector<int>)':
palindromic.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < v.size(); ++i) {
      |                     ~~^~~~~~~~~~

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