Submission #66768

#	Time	Username	Problem	Language	Result	Execution time	Memory
66768		Abelyan	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	53 ms	5036 KiB

palindromic

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 100006;
const long long INF = (ll)1000000000000000007;
const ll P = 13084673;


void solve() {
	string s;
	cin >> s;
	int i = 0, j = s.length() - 1, ans = 0;
	ll hash1 = 0, hash2 = 0, pw = 1;
	while (i < j) {
		hash1 += (ll)(s[i] - 'a' + 1)*pw;
		hash2 = hash2*P + (ll)(s[j] - 'a' + 1);
		//cout << hash1 << " " << hash2 << endl;
		pw *= P;
		i++;
		j--;
		if (hash1 == hash2) {
			ans += 2;
			pw = 1;
			hash2 = 0;
			hash1 = 0;
		}
	}
	if (pw == 1 && i==j+1)
		cout << ans << endl;
	else
		cout << ans + 1 << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

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