Submission #313720

#	Time	Username	Problem	Language	Result	Execution time	Memory
313720		bigg	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	523 ms	42732 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
typedef long long ll;
ll hash1[MAXN], hash2[MAXN];
ll pp1[MAXN], pp2[MAXN];
ll p1 = 37, p2 = 101;
pair<ll, ll>  subhash(int i, int j){
	return make_pair(hash1[i] - (j ? hash1[j - 1] * pp1[i - j + 1] : 0),
					 hash2[i] - (j ? hash2[j - 1] * pp2[i - j + 1] : 0));
}
string s;
int n;
void resetandin(){
	cin >> s;
	n = s.length();
	hash1[0] = hash2[0] = s[0];
	for(int i = 1; i < n; i ++){
		hash1[i] = hash1[i-1] * p1 + s[i];
		hash2[i] = hash2[i-1] * p2 + s[i];
	}
}


int main(){
	pp1[0] = pp2[0] = 1;
	for(int i = 1; i < MAXN; i++){
		pp1[i] = pp1[i-1] * p1;
		pp2[i] = pp2[i-1] * p2;
	}
	int t;
	cin >> t;
	while(t--){
		resetandin();
		int ans = 0;
		int esq = 0, dir = n - 1; 
		for(int i = 0; i < n/2; i++){
			// esq.push_back(s[i]);
			// dir = (s[s.length()-i-1]) + dir;
		//	printf("%d %d %d %d\n",i, esq, dir, n-i-1 );
		//	printf("%lld %lld\n", subhash(i, esq).first, subhash(dir, n - i - 1).second);
			if(subhash(i, esq) == subhash(dir, n - i - 1)){
				esq = i+1;
				dir = n - i - 2;
				ans+=2;
			}
		}
		if(s.length()%2 ||esq < n/2)ans++;
		cout << ans << endl;
	}
}

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