Submission #147196

#	Time	Username	Problem	Language	Result	Execution time	Memory
147196		MvC	Palindromic Partitions (CEOI17_palindromic)	C++11	100 / 100	4747 ms	26488 KiB

palindromic

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "boxes.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mod=1e9+7;
using namespace std;
int n,i,j,rs,f[nmax],x,t;
ll p[]={31,67},m[]={1000003,1000000007},pw[2][nmax],in[2][nmax],hs[2][nmax];
string s;
ll bn(ll x,ll p,ll md)
{
	if(x==1)return 1;
	ll rs=1;
	while(p)
	{
		if(p&1LL)rs=(rs*x)%md;
		x=(x*x)%md;
		p>>=1LL;
	}
	return rs;
}
bool eq(int L,int R,int A,int B)
{
	ll x[2][2];
	int l[2],r[2];
	l[0]=L,l[1]=A,r[0]=R,r[1]=B;
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<1;j++)
		{
			x[i][j]=hs[j][r[i]];
			if(l[i])x[i][j]=(x[i][j]-hs[j][l[i]-1]+m[j])%m[j];
			x[i][j]=(x[i][j]*bn(pw[j][l[i]],m[j]-2,m[j]))%m[j];
		}
	}
	for(int i=0;i<1;i++)if(x[0][i]!=x[1][i])return 0;
	return 1;
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>s;
		n=s.size();
		for(i=0;i<n;i++)
		{
			if(i==0)
			{
				for(j=0;j<1;j++)
				{
					pw[j][i]=1;
					hs[j][i]=s[i];
					//in[j][i]=1;
				}
			}
			else
			{
				for(j=0;j<1;j++)
				{
					pw[j][i]=(pw[j][i-1]*p[j])%m[j];
					hs[j][i]=(hs[j][i-1]+pw[j][i]*s[i])%m[j];
					//in[j][i]=bn(pw[j][i],m[j]-2,m[j]);
				}
			}
		}
		rs=0;
		j=0;
		for(i=0;i<n/2;i++)
		{
			if(eq(j,i,n-i-1,n-j-1))
			{
				rs++;
				j=i+1;
			}
		}
		rs*=2;
		if(n%2==1 || j<n/2)rs++;
		cout<<rs<<endl;
	}
	return 0;
}

Compilation message (stderr)

palindromic.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
palindromic.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")

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