제출 #939254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
939254		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	51 ms	11824 KiB

palindromic

#include "bits/stdc++.h"

using namespace std;

#define int long long

const int p = 31;
const int m = 1e9 + 9;

long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

void solve(){	
	
	string s;
	cin >> s;
	int n = s.size();
	int l = 0,r = n - 1;
	int count = 0;
	while(l < r){
		int pref = 0,suff = 0;
		int p_powl = 1,p_powr = 1;
		pref = (pref + (s[l] - 'a' + 1) * p_powl) % m;
		p_powl = (p_powl * p) % m;
		
		suff = (suff + (s[r] - 'a' + 1) * p_powr) % m;
		p_powr = (p_powr * p) % m;
		l++;
		r--;
		while(l < r && pref != suff){
			pref = (pref + (s[l] - 'a' + 1) * p_powl) % m;
			p_powl = (p_powl * p) % m;
			suff = (suff * p) % m;
			suff = (suff + (s[r] - 'a' + 1)) % m;
			p_powr = (p_powr * p) % m;
			l++;
			r--;
		}
		if(pref == suff){
			count += 2;
		} else if(l > r){
			count++;
		}
	}
	if(l == r){
		count++;
	}
	cout << count << "\n";
}
//(h[i] - h[j]) * (h[i] - h[j]) + pref[i] - pref[j + 1]
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
}	

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