Submission #606918

#	Time	Username	Problem	Language	Result	Execution time	Memory
606918		pakhomovee	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	143 ms	27572 KiB

palindromic

#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define int long long
const int mod = 1e9 + 9;
const int p = 29;
const int maxn = 1e6 + 10;
int P[maxn];

void hs(vector<int> &h, string &s) {
    for (int i = 1; i <= s.size(); ++i) {
        h[i] = (h[i - 1] * p + (s[i - 1] - 'a' + 1)) % mod;
    }
}

int hsh(int l, int r, vector<int> &h) {
    return ((h[r] - h[l - 1] * P[r - l + 1]) % mod + mod) % mod;
}

void solve() {
    string s;
    cin >> s;
    int i = 0;
    int ans = 0;
    vector<int> h(s.size() + 1, 0);
    hs(h, s);
    while (i <= (s.size() - 1) / 2) {
        int len = 1;
        bool ok = false;
        for (; i + len <= s.size() / 2; ++len) {
            if (hsh(i + 1, i + len, h) == hsh(s.size() - i - len + 1, s.size() - i, h)) {
                ok = true;
                break;
            }
        }
        i += len;
        ans += 1 + ok;
    }
    cout << ans << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    P[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        P[i] = (P[i - 1] * p) % mod;
    }
    int t;
    cin >> t;
    while (t--) solve();
}

Compilation message (stderr)

palindromic.cpp: In function 'void hs(std::vector<long long int>&, std::string&)':
palindromic.cpp:14:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 1; i <= s.size(); ++i) {
      |                     ~~^~~~~~~~~~~
palindromic.cpp: In function 'void solve()':
palindromic.cpp:30:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     while (i <= (s.size() - 1) / 2) {
      |            ~~^~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:33:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (; i + len <= s.size() / 2; ++len) {
      |                ~~~~~~~~^~~~~~~~~~~~~~~

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