Submission #199669

#	Time	Username	Problem	Language	Result	Execution time	Memory
199669		algorithm16	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	557 ms	27952 KiB

palindromic

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
typedef long long int llint;
llint h[1000005],p=31337,pot[1000005];
llint get(int a,int b) {
	llint ret=h[b];
	if(a==0) return ret;
	return ret-h[a-1]*pot[b-a+1];
}
int main()
{
	int t;
	cin >> t;
	for(int i=0;i<t;i++) {
		string s;
		cin >> s;
		h[0]=s[0]-'a';
		pot[0]=1;
		pot[1]=p;
		for(int j=1;j<s.size();j++) {
			h[j]=h[j-1]*p+s[j]-'a';
			pot[j+1]=pot[j]*p;
		}
		int x1=0,x2=0,y=s.size()-1,cnt=0;
		while(x2<y) {
			if(get(x1,x2)==get(y-(x2-x1),y)) {
				cnt+=2;
				y-=(x2-x1)+1;
				x1=x2+1;
				x2+=1;
			}
			else x2+=1;
		}
		if(x2<=y) cnt+=1;
		cout << cnt << "\n";
	}
	return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:22:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<s.size();j++) {
               ~^~~~~~~~~

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