oj.uz

Submission #915843

# Submission time Handle Problem Language Result Execution time Memory
915843 2024-01-24T18:59:52 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 157 ms 3540 KB 
#include <bits/stdc++.h>
#include <cassert>

#define MAX_WORD_LENGTH 5100000

int longest_palindromic_partition(const std::string& word) {
    const int n = word.length();
    const unsigned int base = 131;
    int done_chars = 0;
    int n_chunks = 0;

    while (done_chars * 2 < n) {
        unsigned int left_hash = 0, right_hash = 0;
        unsigned int base_power = 1;

        for (int chunk_size = 1; true; chunk_size++) {
            const int l = done_chars;
            const int r = n - done_chars - chunk_size;

            if (l + chunk_size - 1 >= r) {
                return n_chunks + 1;
            }

            base_power = (chunk_size == 1) ? 1 : base_power * base;
            left_hash += static_cast<unsigned int>(word[l + chunk_size - 1]) * base_power;
            right_hash = static_cast<unsigned int>(word[r]) + right_hash * base;

            if (left_hash == right_hash && word.compare(l, chunk_size, word, r, chunk_size) == 0) {
                n_chunks += 2;
                done_chars += chunk_size;
                break;
            }
        }
    }

    return n_chunks;
}

int main() {
    int n;
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        std::string word;
        std::cin >> word;
        assert(word.length() <= MAX_WORD_LENGTH);
        std::cout << longest_palindromic_partition(word) << std::endl;
    }

    return 0;
}

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 344 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 344 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 0 ms 392 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 344 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 0 ms 392 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 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 344 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 0 ms 392 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 157 ms 3540 KB Output is correct
15 Correct 76 ms 3184 KB Output is correct
16 Correct 128 ms 3192 KB Output is correct
17 Correct 81 ms 1884 KB Output is correct