Submission #1248254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248254		islam_2010	Palindromic Partitions (CEOI17_palindromic)	C++20	35 / 100	1 ms	584 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 = 5005;
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];
int invp[sz];
int pp = 31;
int shash[sz];

int get(int l, int r) {
    return ((shash[r] - shash[l - 1] + mod) * invp[l - 1]) % 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();
        for (int i = 0; i <= n; i++) shash[i] = 0;

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

        int l = 1, r = n;
        int ans = 0;
        while (l < r) {
            int len = r - l + 1;
            bool ok = false;
            for (int k = 1; k <= (r - l + 1) / 2; k++) {
                if (get(l, l + k - 1) == get(r - k + 1, r)) {
                    ans += 2;
                    l = l + k;
                    r = r - k;
                    ok = true;
                    break;
                }
            }
            if (!ok) break;
        }
        if (l <= r) ans++; 
        cout << ans << '\n';
    }
}

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