Submission #320619

#	Time	Username	Problem	Language	Result	Execution time	Memory
320619		woldis4	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	3402 ms	18204 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int XN = 1e6+7, md = 1e9+7, base = 257;

ll t, n, p[XN], pw[XN];
string s;

ll tavan(ll a, ll b){
	if (b == 0)	return 1;
	ll adad = tavan(a, b/2);
	return (adad*adad % md) * max(1LL, (b%2)*a) % md;
}

ll substr(int L, int R){
	if (L == 0)	return p[R];
	return ((p[R]-p[L-1]+md) % md) * tavan(pw[L], md-2) % md;
}

void pre(){
	p[0] = int(s[0]);
	for (int i = 1; i < n; ++i)	p[i] = p[i-1] + pw[i]*ll(s[i]), p[i] %= md;
}

int main(){
	cin >> t;
	pw[0] = 1;
	for (int i = 1; i < XN; ++i)	pw[i] = (pw[i-1]*base)%md;
	while (t--){
		cin >> s;
		n = s.size();
		pre();
		ll L = 0, R = n-1, cnt1 = 0, cnt2 = n-1, ans = 0;
		ll flg = 1;
		while (R > L){
			if (substr(cnt1, L) == substr(R, cnt2)){
				if (n%2 == 0 && L == n/2-1 && R == n/2)	flg = 0;
				cnt1 = L+1, cnt2 = R-1, ans += 2;
			}
			++L, R--;
		}
		cout << ans+flg << '\n';
	}
	return 0;
}

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