Submission #319751

#	Time	Username	Problem	Language	Result	Execution time	Memory
319751		armanmohammadi	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	85 ms	9352 KiB

palindromic

//in the name of god
//if you read this code please search about imam hussain
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define endl "\n"
#define X first
#define Y second
#define pii pair<int,int>
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)

const int maxn=1e6+5;
const int mod=1e9+7;
const int inf=1e9;
const int del=728729;
const int pr =  637;
ll poww(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));}
string s  ; 
ll tav[maxn] ;
ll h[maxn]  ;
ll L ;
ll R ;
ll sz ;
ll n  ;
ll l ;
ll r ;
ll mid ;
ll b ;
ll ans ;
ll lh ;
ll rh ;
ll cnt  ;
ll t;
int main()
{
	int t ; 
	migmig; 
	tav[0] = 1 ; 
	for(int i = 1; i < maxn ; i ++ )
	{
		tav[i] = tav[i-1] * pr % mod ; 
	}
	cin>> t ; 
	for(int i = 0 ; i < t  ;i++){
	ans = 0 ; 
	cin>>s ; 
	L= 0 ;
	R = s.size() - 1 ;
	lh = rh = 0 ;
	cnt = 0 ; 
	for(; L < R ; L++ , R-- , cnt++){
		lh = (lh * pr % mod + s[L]) % mod ;
		rh = (rh + tav[cnt] * s[R] % mod ) % mod ; 
		if(lh == rh)
		{
			ans += 2 ; 
			lh = rh = cnt = 0 ; cnt = -1 ; 
		}
	}
	if(s.size() % 2 == 1 || lh != rh)
	ans ++ ; 
	cout<<ans << endl ; 
	}
}
 
 

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