Submission #1138004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138004		cpismayilmmdv985	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	0 ms	320 KiB

palindromic

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp> 
// #include <ext/pb_ds/assoc_container.hpp> 

using namespace __gnu_pbds; 
using namespace std;

// typedef tree<array<int, 2>, null_type,less<array<int, 2>>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

template<typename T1, typename T2>ostream& operator<<(ostream &os, const pair<T1, T2> &p) {return os << '{' << p.first << ", " << p.second << '}';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K, V>& m) {os << "{";for (auto it = m.begin(); it != m.end(); ++it) {if (it != m.begin()) os << ", "; os << it->first << " : " << it->second;}return os << "}";}

void debug() { cerr << endl; }
template<typename Head, typename... Tail>
void debug(Head H, Tail... T) { cerr << H; debug(T...); }
#ifdef VOID_DEBUG
#define deb(...) cerr << '[' << __FILE__ << ':' << __LINE__ << "] (" << #__VA_ARGS__ << "):", debug(__VA_ARGS__)
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define deb(...)
#endif

const int MXN = 2e5 + 5;
const int MOD = 1e9 + 7;

void run_case() {
    string str;
    cin >> str;
    int N = str.length(), P = 47;
    vector<int> pw(N + 1), hashing(N + 1);
    pw[0] = 1;

    for (int i = 1; i <= N; i++) {
        pw[i] = 1LL * pw[i - 1] * P % MOD;
        pw[i] %= MOD;
    }

    for (int i = 1; i <= N; i++) {
        hashing[i] = hashing[i - 1] + 1LL * (str[i - 1] - 'a' + 1) * pw[i - 1] % MOD;
        hashing[i] %= MOD;
    }

    auto check_equal = [&](const int &a, const int &b, const int &l) -> bool {
        int h1 = (hashing[a + l - 1] - hashing[a - 1] + MOD) % MOD;
        int h2 = (hashing[b + l - 1] - hashing[b - 1] + MOD) % MOD;
        return 1LL * h1 * pw[b - a] % MOD == h2;
    };

    int L = 1, R = N, ans = 1;

    while (L < R) {
        bool stop = true;

        for (int i = 1; i < R - L + 1; i++) {
            if (check_equal(L, R - i + 1, i)) {
                ans += 2;
                L += i;
                R -= i;
                stop = false;
                break;
            }
        }

        if (stop) 
            break;
    }

    cout << ans << '\n';
    return;
}

int main() {
#ifndef VOID_DEBUG
    cin.tie(nullptr)->sync_with_stdio(false);
#endif

    int test_case = 1;
    cin >> test_case;
    
    for (int num_case = 1; num_case <= test_case; num_case++) 
        run_case();
    
    return 0;
}

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