Submission #1248257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248257		islam_2010	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	178 ms	26656 KiB

palindromic

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
 
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair<int, int>
#define mpr make_pair
#define fi first
#define se second
#define int long long
#define Local
const int sz = 1e6+5;
const long long inf = 1e9 + 7;
const int mod = 1e9 + 7;
 
template<typename Iterator>
void read(Iterator b, Iterator e) {
    while (b != e) {
        cin >> *b++;
    }
}
 
int bin_pow(int x, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * x) % mod;
        }
        x = (x * x) % mod;
        b >>= 1;
    }
    return res;
}
int p[sz], invp[sz], shash[sz], pp = 31;
int get_hash(int l, int r) {
    return ((shash[r] - shash[l - 1] + mod) * invp[l]) % mod;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        // freopen("main.in", "r", stdin);  // MIND IT BEFORE SUBMIT
        // freopen("main.out", "w", stdout);
    #endif
    p[0] = 1;
    for (int i = 1; i < sz; i++) {
        p[i] = (p[i - 1] * pp) % mod;
    }
    for (int i = 0; i < sz; i++) {
        invp[i] = bin_pow(p[i], mod - 2);
    }

    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = s.size();

        s = "$" + s;  

        shash[0] = 0;
        for (int i = 1; i <= n; i++) {
            shash[i] = (shash[i - 1] + p[i] * (s[i] - 'a' + 1)) % mod;
        }

        int l = 1, r = n;
        int res = 0;

        for (int i = 1; i <= n / 2; i++) {
            if (get_hash(l, i) == get_hash(n - i + 1, r)) {
                res+=2;
                l = i + 1;
                r = n - i;
            }
        }

        cout << res + (l <= r) << '\n';
    }
}

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