oj.uz

Submission #856377

# Submission time Handle Problem Language Result Execution time Memory
856377 2023-10-03T09:25:57 Z Cyanmond Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 341 ms 23940 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()

using i64 = long long;

using u64 = unsigned long long;
constexpr u64 mod = (1ull << 61) - 1;
constexpr u64 base = 121907;

u64 safeMod(__uint128_t v) {
    return v % mod;
}

struct SH {
    static u64 mul(u64 a, u64 b) {
        __uint128_t x = (__uint128_t)(a) * (__uint128_t)(b);
        return safeMod(x % (__uint128_t)mod);
    }

    int n;
    string S;
    vector<u64> hash;

    SH(string s) : S(s) {
        n = (int)S.size();
        hash.assign(n + 1, 0);
        rep(i, 0, n) {
            hash[i + 1] = safeMod(mul(hash[i], base) + (u64)(S[i]));
        }
    }
};

void main_() {
    string S;
    cin >> S;
    const int N = (int)S.size();
    string A = S.substr(0, N / 2), B = S.substr(N - N / 2, N / 2);
    const int M = (int)A.size();
    vector<u64> baseTable(M + 10);
    baseTable[0] = 1;
    rep(i, 1, M + 10) baseTable[i] = SH::mul(baseTable[i - 1], base);

    SH ha(A), hb(B);

    auto judge = [&](int l, int r) {
        u64 hs1 = safeMod(ha.hash[r] + mod - SH::mul(ha.hash[l], baseTable[r - l]));
        u64 hs2 = safeMod(hb.hash[M - l] + mod - SH::mul(hb.hash[M - r], baseTable[r - l]));
        return hs1 == hs2;
    };

    int l = 0, r = 0;
    int ans = 0;
    while (l != M) {
        while (r != M) {
            ++r;
            if (judge(l, r)) {
                break;
            }
        }
        if (not judge(l, r)) {
            ++ans;
            break;
        }
        ans += 2;
        l = r;
        if (l == M) {
            if (N % 2 == 1) ++ans;
            break;
        }
    }
    if (N == 1) ++ans;
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) main_();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 4 ms 600 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 588 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 4 ms 600 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 588 KB Output is correct
14 Correct 320 ms 21212 KB Output is correct
15 Correct 171 ms 20172 KB Output is correct
16 Correct 341 ms 23940 KB Output is correct
17 Correct 172 ms 13740 KB Output is correct