Submission #941221

#	Time	Username	Problem	Language	Result	Execution time	Memory
941221		viwlesxq	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	53 ms	12800 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
	return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
	return a < b ? (a = b) == b : false;
}

const int p = 31;
const int m = 1e9 + 9;

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t; cin >> t;
	while (t--) {
		string s; cin >> s;
		int l = 0, r = size(s) - 1;
		int res = 0;
		while (l < r) {
			int l_hash = s[l++] - 'a' + 1, r_hash = s[r--] - 'a' + 1, p_pow = p;
			while (l < r && l_hash != r_hash) {
				l_hash = (l_hash + (s[l] - 'a' + 1) * p_pow % m) % m;
				r_hash = r_hash * p % m;
				r_hash = (r_hash + s[r] - 'a' + 1) % m;
				l++, r--;
				p_pow = p_pow * p % m;
			}
			if (l_hash == r_hash) res += 2;
			else if (l != r) res++;
		}
		if (l == r) res++;
		cout << res << '\n';
	}
}

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