Submission #161020

#	Time	Username	Problem	Language	Result	Execution time	Memory
161020		nvmdava	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	643 ms	58260 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 1000002
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007LL

ll MOD1 = 1000000207;
ll MOD2 = 1000000009;
int p = 29;

string s;

ll h1[N], h2[N];

ll po1[N], rpo1[N];
ll po2[N], rpo2[N];

ll binpow(ll a, ll b, ll m){
	ll s = 1;
	while(b){
		if(b & 1)
			s = s * a % m;
		b >>= 1;
		a = a * a % m;
	}
	return s;
}

pair<ll, ll> get(int l, int r){
	pair<ll, ll> res;
	res.ff = (h1[r] - h1[l - 1]) * rpo1[l] % MOD1;
	res.ss = (h2[r] - h2[l - 1]) * rpo2[l] % MOD2;
	if(res.ss < 0)
		res.ss += MOD2;
	if(res.ff < 0)
		res.ff += MOD1;
	return res;
}

void go(){
	cin>>s;
	int n = s.size();
	for(int i = 1; i <= n; i++){
		h1[i] = (h1[i - 1] + po1[i] * (s[i - 1] - 'a')) % MOD1;
		h2[i] = (h2[i - 1] + po2[i] * (s[i - 1] - 'a')) % MOD2;
	}

	int l = 1, r = n;
	int ans = 0;

	for(int i = 1; i < r; i++){
		if(get(l, i) == get(r - (i - l), r)){
			ans += 2;
			// cout<<l<<' '<<i<<' '<<r - (i - l)<<' '<<r<<'\n';
			r = r - (i - l) - 1;
			l = i + 1;
			if(l == r)
				break;
		}
	}

	if(l <= r)
		++ans;

	cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
	h1[0] = 1;
	h2[0] = 1;
	po1[1] = po2[1] = rpo1[1] = rpo2[1] = 1;
	
	ll rp1, rp2;
	
	rp1 = binpow(p, MOD1 - 2, MOD1);
	rp2 = binpow(p, MOD2 - 2, MOD2);

	for(int i = 2; i < N; i++){
		po1[i] = po1[i - 1] * p % MOD1;
		po2[i] = po2[i - 1] * p % MOD2;
		rpo1[i] = rpo1[i - 1] * rp1 % MOD1;
		rpo2[i] = rpo2[i - 1] * rp2 % MOD2;
	}

	cin>>t;
    while(t--){
    	go();
    }
}

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