Submission #535883

#	Time	Username	Problem	Language	Result	Execution time	Memory
535883		xuliu	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	14 ms	15956 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

const int N = 1e6 + 4;
const ll mod1 = 1e9 + 7, mod2 = 999999323, base = 2131;
ll powbase[N][2];

ll mul(ll a, ll b, ll mod) { return (a*b)%mod; }
ll del(ll a, ll b, ll mod) {
	a -= b;
	a %= mod;
	if(a < 0) a += mod;
	return a;
}

struct H {
	vector<ll> h1, h2;
	int n;
	H(string s) {
		n = (int) s.size();
		h1.assign(n+1, 0); h2.assign(n+1, 0);
		for(int i=1; i<=n; i++) {
			h1[i] = (mul(h1[i-1], base, mod1) + (s[i-1]-'a'+1))%mod1;
			h2[i] = (mul(h2[i-1], base, mod2) + (s[i-1]-'a'+1))%mod2;
		}
	}
	pair<ll, ll> substr(int l, int r) {
		if(l > r) return {0, 0};
		if(r > n) return {0, 0};
		ll r1 = del(h1[r], mul(h1[l-1], powbase[r-l+1][0], mod1), mod1);
		ll r2 = del(h2[r], mul(h2[l-1], powbase[r-l+1][1], mod2), mod2);
		return {r1, r2};
	}
};

void solve() {
	string s; cin>>s; int n = (int) s.size();
	H h(s);
	int ans = 1, px = 0;
	for(int i=1; i<=(n/2); i++) {
		if(h.substr(px+1, i) == h.substr(n-i+1, n-px)) {
			px = i;
			ans+=2;
		}
	}
	cout<<ans<<"\n";
}

void prepare() {
	powbase[0][0] = powbase[0][1] = 1;
	for(int i=1; i<N; i++) {
		powbase[i][0] = mul(powbase[i-1][0], base, mod1);
		powbase[i][1] = mul(powbase[i-1][1], base, mod2);
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	prepare();
	int tc; cin>>tc;
	while(tc--) {
		solve();
	}
}

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