Submission #318159

#	Time	Username	Problem	Language	Result	Execution time	Memory
318159		RohamIzadidoost	Palindromic Partitions (CEOI17_palindromic)	C++14	0 / 100	9 ms	8172 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  ;

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() ; 
	h[0] = s[0] ; 
	for(int i = 1 ; i < n ; i ++ ){
		h[i] = h[i-1] * H % mod + s[i] ; 
		h[i] %= mod ; 
	}
	L= 0 , R = n - 1 ;  
	while(n > 0){
		l = 1 , r = n/2 + 1 , b = 1 ; 
		if(r-l  == 0){
			n = 0 ; 
			ans ++ ;
			break ; 
		}
		while(r-l>1){
			mid = (l + r)/ 2 ; 
			if(check(mid)) l = mid , b = 0 ; 
			else r = mid ; 
		}
		if(!check(l)){
			n = 0 ; 
			ans ++ ; 
		}else{
			L += l ; 
			R -= l ;
			ans += 2 ; 
			n -= 2 * l ;  
		//	cout<<ans << " " << l <<" " << L <<" " << R <<" " << n << endl ; 
		}
	}
	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: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40