Submission #161012

#	Time	Username	Problem	Language	Result	Execution time	Memory
161012		nvmdava	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	61 ms	15992 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

int MOD1 = 1000000007;
int MOD2 = 1000000009;
int p = 35;

string s;

int h1[N], h2[N];

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

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

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

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

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

	for(int i = 1; i <= (l + r) / 2; i++){
		if(get(l, i) == get(r - (i - l), r)){
			ans += 2;
			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[0] = po2[0] = rpo1[0] = rpo2[0] = 1;
	
	int rp1, rp2;
	
	rp1 = binpow(p, MOD1 - 2, MOD1);
	rp2 = binpow(p, MOD2 - 2, MOD2);

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

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

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