oj.uz

Submission #924933

# Submission time Handle Problem Language Result Execution time Memory
924933 2024-02-10T05:14:48 Z sleepntsheep Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>

#define N 200005
#define ALL(x) begin(x), end(x)
using namespace std;

#define int long long

constexpr long long B { 103 }, M { 1000000007 };


int docase()
{
    string s;
    cin >> s;
    int n = s.size(), z {};
    s = "0" + s;
    vector<int> h(2*n+2, 0), pw(2*n+2, 1), ipw(2*n+2, 1);

    auto bpow = [&](auto &&bpow, long long a, long long b) -> long long {
        if (!b) return 1;
        auto r = bpow(bpow, a, b>>1);
        if (b&1) return r*r%M*a%M;
        return r*r%M;
    };
    for (auto &c : s) c -= 'a';

    for (int i = 1; i <= n; ++i)
        pw[i] = 1ll * pw[i-1] * B % M, ipw[i] = bpow(bpow, pw[i], M-2);

    for (int i = 1; i <= n; ++i)
        h[i] = (h[i-1] + ((long long)s[i] * pw[i] % M)) % M;


    auto sub = [&](int l, int r){
        auto base = (h[r] - h[l-1] + M) % M;
        (base *= ipw[l]) %= M;
        return base;
    };

    for (int f, i = 1, j; i <= n/2;)
    {
        f = 0;
        for (j = i; j <= n/2; ++j)
        {
            if (sub(i, j) == sub(n-j+1, n-i+1))
            {
                z += 2;
                f = 1;
                break;
            }
        }
        if (!f) ++z;
        i = j + 1;
        if (n % 2 and i > n / 2 and f) ++z;
    }

    cout << z << '\n';

    return 0;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--) docase();
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -