Submission #1326729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326729		witek_cpp	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	74 ms	25032 KiB

palindromic

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

typedef long long ll;

#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define f(i, a, b) for (int i = a; i < b; i++)
#define rep(i, a) f(i, 0, a)
#define int ll
#define tv(a, x) for (auto& a : x)
#define DUZO 1000000000000000000LL
#define en "\n"
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vii = vector<pii>;

const int MOD = 1514312797;
const int P = 40429429;
const int MAXN = 1'000'007;

int n;
string s;

vi war(MAXN);
vi hasz;

void prep() {
    war[0] = 1;
    f(i, 1, MAXN) war[i] = (P * war[i - 1])%MOD;
}

void zrob_hash() {
    hasz = {};
    hasz.resize(n +1);
    hasz[0] = 0;
    f(i, 1, n + 1) {
        hasz[i] = (hasz[i - 1] + (s[i - 1] * war[i]))%MOD;
    }
}

int get_hash(int l, int r) {
    return ((hasz[r] - hasz[l - 1] + MOD) * war[n - r])%MOD;
}

void solve() {
    cin >> s;
    n = sz(s);
    zrob_hash();
    int ak = 1;
    int wnk = 1;
    f(i, 1, (n/2) + 1) {
        int h1 = get_hash(ak, i);
        int h2 = get_hash(n - i + 1, n - ak + 1);
        if (h1 == h2) {
            wnk+=2;
            if ((i * 2) == n) wnk--;
            ak = i + 1;
        }
    }
    cout << wnk << en;
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int q = 1;
    prep();
    cin >> q;
    while (q--) {
        solve();
    }
    return 0;
}

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