Submission #1135350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135350		qrn	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	129 ms	18868 KiB

palindromic

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

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);
 
#define pb push_back
#define ins insert
 
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long
#define endl "\n"
 
const intt mod = 1e9 + 7;
const intt base = 47;
const intt inf = 1e9;
const intt mxN = 1e6 + 5;
const intt maxA = 1e5 + 5;
const intt L = 23;

vector<intt> pw(mxN), hsh(mxN);

bool check(intt sol, intt sag, intt len) {
    intt h1 = (hsh[sol + len - 1] - hsh[sol - 1] + mod) % mod;
    intt h2 = (hsh[sag + len - 1] - hsh[sag - 1] + mod) % mod;
    return ((h1 * pw[sag - sol]) % mod == h2);
}

void solve() {
    string s;
    cin >> s;

    intt n = s.size();
    pw[0] = 1;
    hsh[0] = 0;
    for(int i = 1; i < n; i++) {
        pw[i] = pw[i-1] * base;
        pw[i] %= mod;
    }

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

    intt l = 1, r = n, len = 1, ans = 0;

    while(l <= r) {
        // cout << l << " " << r << endl;
        intt tmpl = l, tmpr = r;
        while(!check(tmpl, tmpr, len)) {
            if(tmpl >= tmpr) break;
            len++;
            tmpr--;
        }
        if(l + len - 1 >= r - len + 1) {
            ans++;
            break;
        } else {
            l = l + len;
            r = r - len;
            ans += 2;
        }
        len = 1;
    }
    cout << ans << endl;
}

// asd

signed main() {
    SPEED;  
    intt tst = 1;
    cin >> tst;
    while (tst--) {
        solve();
    }
}

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