Submission #525066

#	Time	Username	Problem	Language	Result	Execution time	Memory
525066		Yazan_Alattar	Palindromic Partitions (CEOI17_palindromic)	C++14	0 / 100	0 ms	204 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 Hash {
  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;
  }
};

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--){
		string s;
		cin >> s;
		Hash Hs; Hs.build(s);
		int n = s.size(), st = 0, ans = 0;
		for(int i = 0; i < n / 2; ++i){
			if(Hs.get(st, i) == Hs.get(n - i - 1, n - st - 1)){
				ans += 2;
				st = i + 1;
			}
		}
		cout << ans + 1 << endl;
	}
	return 0;
}

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