Submission #915867

#	Time	Username	Problem	Language	Result	Execution time	Memory
915867		cper	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	71 ms	17144 KiB

palindromic

# include <bits/stdc++.h>

typedef std::string st;
typedef long long ll;

using namespace std;

ll p[1000006], h[1000006];
ll a, n, l, c, i;
ll h1, h2;

st t;

bool f;

bool check_equal(ll a, ll b, ll l) {
    h1 = (h[a + l - 1] - h[a - 1]) * p[b - a];
    h2 = (h[b + l - 1] - h[b - 1]);

    return h1 == h2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a;

    while (a --) {
        cin >> t;

        n = t.size();

        p[0] = 1, p[1] = 47;

        for (i = 2; i < n; i ++) {
            p[i] = p[i - 1] * p[1];
        }

        h[0] = 0;

        for (i = 1; i <= n; i ++) {
            h[i] = h[i - 1] + (t[i - 1] - 'a' + 1) * p[i - 1];
        }

        l = 1, c = 0;

        while (l <= n / 2 + (n % 2)) {
            i = 1, f = false;

            for (; i <= n / 2 - l + 1; i ++) {
                // cout << t.substr(l-1, i) << ' ' << t.substr(n - l - i + 1, i) << '\n';

                if (check_equal(l, n - l - i + 2, i)) {
                    // cout << "fuck you\n";
                    c += 2;
                    l = l + i;
                    f = true;
                    break;
                }
            }

            if (!f) {
                // cout << "HEY\n";
                // cout << l << '\n';
                c ++;
                break;
            }
        }

        cout << c << '\n';
    }
}

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