Submission #511580

#	Time	Username	Problem	Language	Result	Execution time	Memory
511580		Monarchuwu	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	133 ms	28700 KiB

palindromic

#include<iostream>
#include<algorithm>
#include<string>
#include<bitset>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1e6 + 16, mod = 1e9 + 7, base = 331;
const ll mod2 = (ll)mod * mod;
int n;
string s;
ll pw[N], hsh[N];
ll get(int l, int r) {
    return (hsh[r] - hsh[l - 1] * pw[r - l + 1] + mod2) % mod;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    pw[0] = 1;
    for (int i = 1; i < N; ++i)
        pw[i] = pw[i - 1] * base % mod;

    int test; cin >> test; while (test--) {
        cin >> s; n = s.size();
        s = " " + s;

        for (int i = 1; i <= n; ++i)
            hsh[i] = (hsh[i - 1] * base + s[i]) % mod;

        int l(1), r(n), len(0), ans(0);
        while (l < r) {
            ++len;
            if (get(l - len + 1, l) == get(r, r + len - 1))
                ans += 2, len = 0;
            ++l, --r;
        }
        cout << ans + (len > 0 || l == r) << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
4
bonobo
deleted
racecar
racecars
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
3
5
7
1
--------------------------------------------------|
==================================================+
*/

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