Submission #1254368

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

palindromic

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 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;
	}
	
	for(int i = 1 ; i <= n ; i++){
		int ans = n;
	    int k = n - i + 1;
	    for(int j = 0 ; j <= n - 2 * (i - 1) ; j++){
	    	if(get(i , i + j) == get(k - j , k)){
	    		ans = j;
	    		break;
			}
		}
	    nxt[i] = i + ans;
	}
	int l = 0 , r = n;
	int cnt = 0;
	for(int i = 1 ; i <= n ; i++){
		l = nxt[i];
	    r = n - nxt[i] + 1;
	    if(l < r) cnt += 2;
	    else cnt++;
		if(l >= r) break;
	   
	}
	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: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40