Submission #318175

#	Time	Username	Problem	Language	Result	Execution time	Memory
318175		RohamIzadidoost	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	78 ms	9352 KiB

palindromic

#pragma GCC optimize("O2")
#include<bits/stdc++.h>
typedef long long ll ;
#define pll pair<ll , ll >
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
using namespace std;
const int maxn = 1000*1000+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1000696969 ;
const ll mod2 = 1e9 + 7 ; 
const ll H = 1777013 ;
string s  ; 
ll pt[maxn] , h[maxn]  , L , R , sz , n  , l, r  , mid , b   , ans   , lh , rh , cnt  ;

ll hsh(int l , int r){
	if(l == 0 ) return h[r] ; 
	return ( h[r] - h[l-1] * pt[r-l+1] % mod  + mod ) % mod ;  }
 
bool check(int x){
	return( hsh(L , L + x - 1) == hsh(R - x + 1 , R) ) ; 
}
int Main()
{
	ans = 0 ; 
	cin>>s ; n = s.size() ; 
	L= 0 , R = n - 1 ;  lh = 0 , rh = 0 ; 
	cnt = 0 ; 
	for( ; L < R ; L++ , R-- , cnt++){
		lh = (lh * H % mod + s[L]) % mod , rh = (rh + pt[cnt] * s[R] % mod ) % mod ; 
	//	cout<<L <<" " << R <<" " << lh <<" " << rh << endl ; 
		if(lh == rh)
		{
			ans += 2 ; 
			lh = rh = cnt = 0 ; cnt = -1 ; 
		}
	}
	if(n % 2 == 1 || lh != rh)
	ans ++ ; 
	cout<<ans << endl ; 
	return 0 ; 
}

int main()
{
	int t ; 
	migmig; 
	pt[0] = 1 ; 
	for(int i = 1; i < maxn ; i ++ )
	{
		pt[i] = pt[i-1] * H % mod ; 
	}
	cin>> t ; 
	while(t--)
	{
		Main() ; 
	}
}

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