Submission #1135334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135334		qrn	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	2 ms	4928 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 = 3e5 + 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, ans = 0;
    while(l <= r) {
        intt k = 1;
        intt tmpr = r;
        while(!check(l, tmpr, k) && l + k < tmpr) {
            k++;
            tmpr--;
        }
        if(l + k >= tmpr) {
            ans++;
            break;
        } else {
            l += k;
            r -= k;
            // bonobo
            ans += 2;
        }
    }
    cout << ans << endl;
}

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

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