Submission #305138

#	Time	Username	Problem	Language	Result	Execution time	Memory
305138		miss_robot	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	110 ms	26900 KiB

palindromic

#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#define int long long

using namespace std;

const int N = 1e6, A = 987361726, B = 1e9+7;
int t, n, l, sol;
int h[N], p[N];
string s;

void pre(){
	h[0] = s[0];
	p[0] = 1;
	for(int i = 1; i < n; i++){
		h[i] = (h[i-1] * A + s[i]) % B;
		p[i] = (p[i-1] * A) % B;
	}
}

int hsh(int a, int b){
	if(!a) return h[b];
	return (h[b] - h[a-1] * p[b-a+1] + B*B) % B;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> t;
	while(t--){
		cin >> s;
		n = s.size();
		pre();
		l = sol = 0;
		for(int i = 0; i < n/2; i++){
			if(hsh(l, i) == hsh(n-i-1, n-l-1)){
				sol+=2;
				l = i+1;
			}
		}
		if(n%2 || l < n/2) sol++;
		cout << sol << "\n";
	}
}

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