제출 #66104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66104		polyfish	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	213 ms	44600 KiB

palindromic

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 1000007;
const int MOD = 1000000007;

int n;
string s;
int64_t H[MAX_N], pw26[MAX_N];

void init() {
	pw26[0] = 1;
	for (int i=1; i<=n; ++i) {
		H[i] = (H[i-1] * 26+ s[i] - 'a') % MOD;
		pw26[i] = pw26[i-1] * 26 % MOD;
	}
}

int64_t get(int l, int r) {
	return (H[r] - H[l-1] * pw26[r-l+1] % MOD + MOD) % MOD;
}

int solve(int l, int r) {
	if (l>r)
		return 0;
	for (int i=1; i<=(r-l+1)/2; ++i)
		if (get(l, l+i-1)==get(r-i+1, r))
			return solve(l+i, r-i) + 2;
	return 1;
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	int nTest;
	cin >> nTest;
	while (nTest--) {
		cin >> s;
		n = s.size();
		s = '@' + s;
		init();
		//debug(get(1, 2));
		//debug(get(5, 6));
		cout << solve(1, n) << '\n';
	}
}

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