Submission #619063

#	Time	Username	Problem	Language	Result	Execution time	Memory
619063		jophyyjh	Palindromic Partitions (CEOI17_palindromic)	C++14	60 / 100	1121 ms	1648 KiB

palindromic

/**
 * Notes during contest.
 * 
 * ------ A ------
 * In the example, (3,7,6,6) is the set of optimal pillars to select. Well, I assume
 * that the subset of pillars shall be connected in order?
 * 
 * ------ B ------
 * [S1-2] is solvable with a O(n^2) dp (Z-array + dp). I also have a hunch that we
 * can pass [S3] too (#time_limit = 10s). Oh no... I really suck at str processing
 * problems...
 * 
 * ------ C ------
 * 
 * Time Complexity 1: O()
 * Time Complexity 2: O(n^2)
 * Time Complexity 3: O()
 * Implementation 1
*/
 
#include <bits/stdc++.h>
 
typedef int64_t     int_t;
typedef std::vector<int_t>  vec;
 
 
inline vec z_array(const std::string& s) {
    int_t n = s.size();
    vec z(n, 0);
    for (int_t k = 1, x = 0, y = 1; k < n; k++) {
        z[k] = std::max(std::min(z[k - x], y - k + 1), int_t(0));
        while (k + z[k] < n && s[k + z[k]] == s[z[k]])
            x = k, y = k + z[k], z[k]++;
    }
    // std::cerr << "[debug] " << s << std::endl;
    // for (int_t a : z)
    //     std::cerr << a << ' ';
    // std::cerr << std::endl;
    return z;
}
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int_t T;
    std::cin >> T;
    for (int_t tc = 1; tc <= T; tc++) {
        std::string str;
        std::cin >> str;
        int_t n = str.length();
        if (n > 10000) {
            std::cout << "bye\n";
            return 0;
        }
        
        
        vec dp(n, 1);
        for (int_t k = (n - 1) / 2; k >= 0; k--) {
            std::string substr = str.substr(k, n - 2 * k);
            vec Z = z_array(substr);
            for (int_t i = n - 2 * k - 1; i > 0; i--) {
                assert(Z[i] <= n - 2 * k - i);
                if (Z[i] != n - 2 * k - i || 2 * Z[i] > n - 2 * k)
                    continue;
                if (2 * Z[i] == n - 2 * k) {    // even palindrome
                    dp[k] = std::max(dp[k], int_t(2));
                } else {    // odd palindrome
                    dp[k] = std::max(dp[k], dp[k + Z[i]] + 2);
                }
            }
        }
        std::cout << dp[0] << '\n';
    }
}

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