Submission #410377

#	Time	Username	Problem	Language	Result	Execution time	Memory
410377		Blagojce	Palindromic Partitions (CEOI17_palindromic)	C++11	0 / 100	29 ms	16040 KiB

palindromic

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)


using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll inf = 4e9;
const ll mod = 1e9+7;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
ll A = 911382323;
ll B = 972663749;
mt19937 _rand(time(NULL));
clock_t z;
const int mxn = 2e6;
int n;
string s;
ll h[mxn];
ll p[mxn];

ll hsh(int l, int r){
	ll hs = h[r];
	if(l > 0) hs = (hs - h[l-1]*p[r-l+1])%B;
	if(hs < 0) hs += B;
	return hs;
}

void solve(){
	cin >> s;
	n = (int)s.size();
	h[0] = (int)s[0];
	fr(i, 1, n){
		h[i] = (h[i-1]*A + (int)s[i])%B;
	}
	int l = 0;
	int ans = 0;
	fr(r, 0, n/2){
		int lp = n-r-1;
		int rp = n-l-1;
		if(hsh(l, r) == hsh(lp, rp)){
			++ans;
			l = r+1;
		}
	}
	ans *= 2;
	if(l <= n/2) ++ans;
	cout<<ans<<endl;
	
	
}
int main(){
	p[0] = 1;
	fr(i, 1, 2e6){
		p[i] =  (p[i-1]*A)%B;
	}
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	while(t--){
		solve();
	}
}

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