Submission #1312166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312166		kyryl	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	118 ms	19324 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define un unsigned
#define all(v) begin(v), end(v)
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define per(i, a, b) for(ll i = a; i >= b; i--)
#define deb(x) cout << #x << " = " << x << '\n';
#define st first
#define nd second
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
using ll = long long;
const ll LINF = 1e18;
const ll INF = 1e9;
const int N = 1e6 + 5;
const ll M = 1382334427;
ll B;
ll pot[N];
ll suf[N];
mt19937 gen(time(NULL));
void doB(){
	B = uniform_int_distribution<ll>(1, ll(M) - 1)(gen);
}
void dopot(int n){
	pot[0] = 1;
	rep(i, 1, n + 2){
		pot[i] = pot[i - 1] * B % M;
	}
}
void dosuf(string& s, int n){
	suf[n] = 0;
	per(i, n - 1, 0){
		suf[i] = (suf[i + 1] * B + s[i]) % M;
	}
}
ll prze(int i, int j){ // otwarty
	return (suf[i] - (suf[j] * pot[j - i] % M) + M) % M;
}
void solve(){
	string s;
	cin >> s;
	int n = s.size();
	doB();
	dopot(n);
	dosuf(s, n);
	int l0 = 0, l1 = 0, r0 = n, r1 = n;
	int odp = 0;
	rep(i, 0, n / 2){
		l1++;
		r0--;
		if(prze(l0, l1) == prze(r0, r1)){
			odp += 2;
			l0 = l1;
			r1 = r0;
		}
	}
	if(n % 2){
		odp++;
	}
	else{
		if(l0 != l1)odp++;
	}
	cout << odp << '\n';
}
int main(){
    fast
	int t;
	cin >> t;
	while(t--){
		solve();
	}
}

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