Submission #824050

#	Time	Username	Problem	Language	Result	Execution time	Memory
824050		NK_	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	275 ms	34928 KiB

palindromic

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;

const int MOD = 1e9 + 7;

using H = array<int, 2>;
H base = {1007, 513};
H makeH(char c) { return {c, c}; }

H operator+(H l, H r) {
	for(int i = 0; i < 2; i++) if ((l[i] += r[i]) >= MOD) l[i] -= MOD;
	return l;
}

H operator-(H l, H r) {
	for(int i = 0; i < 2; i++) if ((l[i] -= r[i]) < 0) l[i] += MOD;
	return l;
}

H operator*(H l, H r) {
	for(int i = 0; i < 2; i++) l[i] = (l[i] * 1LL * r[i]) % MOD;
	return l;
}
 

V<H> pows{{1, 1}};
struct HASH {
	V<H> cum{{}}; string S;
	void add(char c) { cum.pb(cum.back() * base + makeH(c)); }
	void add(string T) { for(auto c : T) add(c); }
	void extend(int len) { while(sz(pows) <= len) pows.pb(pows.back() * base); }
	H hash(int l, int r) { extend(r-l+1); return cum[r+1] - pows[r-l+1] * cum[l]; }
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int T; cin >> T;
	while(T--) {
		string S; cin >> S;
		int N = sz(S);

		HASH h; h.add(S);
		auto check = [&](int l, int r) {
			return h.hash(l, r) == h.hash(N - 1 - r, N - 1 - l);
		};

		// cout << S << endl;

		int ans = 0;
		int l = 0; int M = N / 2;
		for(int r = 0; r < M; r++) {
			if (check(l, r)) ans += 2, l = r + 1;
		}

		int half = (N + 1) / 2;
		if (l < half) ans++;

		cout << ans << nl;
	}

    return 0;
}			

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