Submission #525070

#	Time	Username	Problem	Language	Result	Execution time	Memory
525070		Yazan_Alattar	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	578 ms	43212 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 200007;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

struct Hash1 {
  ll SEED = 131,MOD = 1e9 + 7;
  vector<ll> ha;
  vector<ll> power;

  void build(string x) {
	power.resize(x.size());
	ha.resize(x.size());
    power[0] = 1;
    for(int i=1; i<(int)power.size(); i++) power[i] = (power[i-1] * SEED)%MOD;
    ha[0] = x[0];
    for(int i=1; i<(int)ha.size(); i++) ha[i] = (ha[i-1] * SEED + x[i])%MOD;
  }
  
  ll get(int i, int j) {
    ll ret = ha[j];
    if (i) ret -= (ha[i-1] * power[j - i + 1])%MOD;
    ret = (ret % MOD + MOD) % MOD;
    return ret;
  }
};

struct Hash2 {
  ll SEED = 101,MOD = 1e9 + 9;
  vector<ll> ha;
  vector<ll> power;

  void build(string x) {
	power.resize(x.size());
	ha.resize(x.size());
    power[0] = 1;
    for(int i=1; i<(int)power.size(); i++) power[i] = (power[i-1] * SEED)%MOD;
    ha[0] = x[0];
    for(int i=1; i<(int)ha.size(); i++) ha[i] = (ha[i-1] * SEED + x[i])%MOD;
  }
  
  ll get(int i, int j) {
    ll ret = ha[j];
    if (i) ret -= (ha[i-1] * power[j - i + 1])%MOD;
    ret = (ret % MOD + MOD) % MOD;
    return ret;
  }
};

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--){
		string s;
		cin >> s;
		Hash1 Hs1; Hs1.build(s);
		Hash2 Hs2; Hs2.build(s);
		int n = s.size(), st = 0, ans = 0;
		for(int i = 0; i < n / 2; ++i){
			if(Hs1.get(st, i) == Hs1.get(n - i - 1, n - st - 1) && Hs2.get(st, i) == Hs2.get(n - i - 1, n - st - 1)){
				ans += 2;
				st = i + 1;
			}
		}
		if(n % 2 || st != n / 2) ++ans;
		cout << ans << endl;
	}
	return 0;
}

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