Submission #227535

#	Time	Username	Problem	Language	Result	Execution time	Memory
227535		nafis_shifat	Palindromic Partitions (CEOI17_palindromic)	C++14	0 / 100	4 ms	256 KiB

palindromic

#include<bits/stdc++.h>
#define pii pair<long,long>
#define ll long long
#define f first
#define s second
using namespace std;
const int mxn=1000008;
const ll p1=20000003,p2=500009,p3=100200011,p4=1e9+9;
char s[mxn];
pii getHash(pii x,ll c)
{
	x.f=x.f*p1 % p3;
	x.s=x.s*p2 % p4;

	x.f+=c*p1;
	x.f%=p3;
	x.s+=c*p2;
	x.s%=p4;
	return x;
}
int solve(int b,int e)
{
	if(b==e)return 1;
	if(e-b==1)
	{
		if(s[b]==s[e])return 2;
		return 1;
	}

	pii h1=make_pair(0,0);
	pii h2=make_pair(0,0);
	
	ll P1=p1,P2=p2;
	while(b<e)
	{
		ll c=s[b]-'a';
		h1={h1.f+ c*P1 % p3, h1.s+ c*P2 % p4};
		h2=getHash(h2,s[e]-'a');
		if(h1==h2)return 2+solve(b+1,e-1);
		b++;e--;

		P1=p1*P1 % p3;
		P2=P2*p2 % p4;
	}
	return 1;
}
void solve()
{
	scanf("%s",s);
	int n=strlen(s);

	int res=solve(0,n-1);
	printf("%d\n",res);
}
int main()
{
	//freopen("input.txt","r",stdin);
	int t=1;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s);
  ~~~~~^~~~~~~~

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