Submission #1254370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254370		mngoc._.	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	104 ms	21484 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
const int base = 311;
const int LOG = 32;
const int MOD = 1e9 + 7;
int hsh[N];
int hsh2[N];
int power[N];
int mngoc[N][LOG];
int nxt[N];
int n , m;
string s;
string t; 
int get(int l , int r){
	return (hsh[r] - hsh[l - 1] * power[r - l + 1]%MOD + MOD) % MOD;
}

void solve(void){
	cin >> s; n = s.size();
	t = s;
	reverse(t.begin() , t.end());
	s = '#' + s;
	t = '#' + t;	
	power[0] = 1;
	hsh[0] = 0 ; hsh2[0] = 0;
	for(int i = 1 ; i <= n ; i++){
		hsh[i] = (hsh[i - 1] * base + (s[i] - 'a' + 1)) % MOD;
		power[i] = (power[i - 1] * base) % MOD;
	}
	
	int l = 1 , r = n;
	int cnt = 0;
	for(int i = 1 ; i <= n / 2 ; i++){
		if(l >= r) break;
        if(get(l , i) == get(r - (i - l) , r)){
        	cnt += 2;
        	r = r - (i - l) - 1;
        	l = i + 1;
		}
	}
	if(l <= (n + 1)/2) cnt++;
	cout << cnt << endl;
	
	
	
}

signed main(void){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	int testCase; cin >> testCase;
	while(testCase--){
		solve();
	}
	return 0;
}

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