Submission #45433

#	Time	Username	Problem	Language	Result	Execution time	Memory
45433		Noam527	Palindromic Partitions (CEOI17_palindromic)	C++11	100 / 100	455 ms	27052 KiB

palindromic

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#include <random>
#include <fstream>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

const int maxn = 1e6 + 1;

const int p[3] = { 157, 163, 167 };
const int mod[3] = { (int)1e9 + 7, (int)1e9 + 9, (int)1e9 + 21 };
ll pw[3][maxn];

void preprocess() {
	for (int i = 0; i < 3; i++) pw[i][0] = 1;
	for (int j = 1; j < maxn; j++)
		for (int i = 0; i < 3; i++)
			pw[i][j] = (pw[i][j - 1] * p[i]) % mod[i];
}

void solve() {
	string s;
	cin >> s;
	int n = s.size();

	int ans = 0;
	int st = 0;
	ll sth[3] = {};
	ll enh[3] = {};
	bool ok;
	for (int i = 0; i < n; i++) {
		if (i >= n / 2) {
			if (n % 2 == 1 || st < i) ans++;
			cout << ans << endl;
			return;
		}
		for (int j = 0; j < 3; j++) {
			sth[j] = (sth[j] + pw[j][i - st] * s[i]) % mod[j];
			enh[j] = (p[j] * enh[j] + s[n - i - 1]) % mod[j];
		}
		ok = true;
		for (int j = 0; j < 3; j++) {
			ok = ok && (sth[j] == enh[j]);
		}
		if (ok) {
			ans += 2;
			st = i + 1;
			for (int j = 0; j < 3; j++)
				sth[j] = enh[j] = 0;
		}
	}
}

int main() {
	fast;
	preprocess();
	int t;
	cin >> t;
	while (t--) solve();
}

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