제출 #1273638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273638		AksLolCoding	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	134 ms	19720 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class HashedString {
  private:
	// change M and B if you want
	static const long long M = 1e9 + 9;
	static const long long B = 9973;

	// pow[i] contains B^i % M
	static vector<long long> pow;

	// p_hash[i] is the hash of the first i characters of the given string
	vector<long long> p_hash;

  public:
	HashedString(const string &s) : p_hash(s.size() + 1) {
		while (pow.size() <= s.size()) { pow.push_back((pow.back() * B) % M); }

		p_hash[0] = 0;
		for (int i = 0; i < s.size(); i++) {
			p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
		}
	}

	long long get_hash(int start, int end) {
		long long raw_val = (p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
		return (raw_val % M + M) % M;
	}
};
vector<long long> HashedString::pow = {1};

void solve() {
    string s;
    cin >> s;
    int n = s.size();

    HashedString hs(s);
    int ans = 0, l = 0, r = n-1, i = 0;
    while (l <= r) {
        if (l + i >= r - i) {
            ans++;
            break;
        }
        ll lh = hs.get_hash(l, l + i), rh = hs.get_hash(r - i, r);
        if (lh == rh) {
            ans += 2;
            l += i + 1;
            r -= i + 1;
            i = 0;
        } else {
            i++;
        }
    }

    // ans
    cout << ans << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(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