Submission #45266

#	Time	Username	Problem	Language	Result	Execution time	Memory
45266		qoo2p5	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	41 ms	38856 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

typedef unsigned long long ull;

const int N = (int) 1e6 + 123;
const ull P = 239;

string s;
ull p[N];

void solve() {
	cin >> s;
	int n = sz(s);
	int res = 0;
	ull left = 0;
	ull right = 0;
	int already = 0;
	int len = 0;
	while (already + len < n / 2) {
		int pos_l = already + len;
		int pos_r = n - already - len - 1;
		left = left * P + s[pos_l];
		right += s[pos_r] * p[len];
		len++;
		if (left == right) {
			already += len;
			len = 0;
			left = 0;
			right = 0;
			res += 2;
		}
	}
	
	if (n % 2 == 1 || left != 0) {
		res++;
	}
	
	cout << res << "\n";
}

void run() {
	p[0] = 1;
	rep(i, 1, N) p[i] = p[i - 1] * P;
	
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
}

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