Submission #713474

#	Time	Username	Problem	Language	Result	Execution time	Memory
713474		Astrayt	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	114 ms	20620 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define int ll
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair

int pw[1000005], P = 41, mod = 998244353;

void solve(){
	string s; cin >> s;
	int n = s.size(), i = 0, j = n - 1, cur_sz = 0, ans = 0;
	int lh = 0, rh = 0;
	while(j - i > 0){
		lh = (lh * P % mod + s[i] % mod);
		rh = (rh + pw[cur_sz] * s[j]) % mod;
		cur_sz++;
		if(lh == rh){
			cur_sz = lh = rh = 0;
			ans += 2;
		}
		i++, j--;
	}
	if(cur_sz != 0 || n % 2) ans++;
	cout << ans << '\n';
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	pw[0] = 1;
	for(int i = 1; i <= 1000000; ++i) pw[i] = pw[i - 1] * P % mod;
	int t = 1; cin >> t;
	while(t--) solve();
}

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