Submission #448822

#	Time	Username	Problem	Language	Result	Execution time	Memory
448822		osmanallazov	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	312 ms	40380 KiB

palindromic

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAKS=1e6+10;
ll v1[MAKS],v2[MAKS],hash1[MAKS],hash2[MAKS];
ll p1=37,p2=101;
pair<ll,ll>subhash(int i, int j){
	return make_pair(hash1[i] - (j ? hash1[j - 1] * v1[i - j + 1] : 0),
					 hash2[i] - (j ? hash2[j - 1] * v2[i - j + 1] : 0));
}
string s;
int n;
void re(){
	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(){
    v1[0]=v2[0]=1;
	for(int i=1;i<MAKS;i++){
		v1[i]=v1[i-1]*p1;
		v2[i]=v2[i-1]*p2;
	}
    int T;
    cin>>T;
    while(T--){
        re();
		int ans=0;
		int e=0,d=n-1;
		for(int i=0;i<n/2;i++){
			if(subhash(i,e)==subhash(d,n-i-1)){
				e=i+1;
				d=n-i-2;
				ans+=2;
			}
		}
		if(s.length()%2 || e<n/2)ans++;
		cout<<ans<<endl;
    }
}

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