Submission #835798

#	Time	Username	Problem	Language	Result	Execution time	Memory
835798		elkernos	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	1 ms	212 KiB

palindromic

// clang-format off
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; }
sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; }
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
struct { template <class T> operator T() { T x; cin >> x; return x; } } in;
#define endl '\n'
#define pb emplace_back
#define vt vector
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using i64 = long long;
// #define int long long
// clang-format on

// clang-format off
template <class T>
T power(T a, i64 b) { T res = 1; for (; b; b /= 2, a *= a) if (b % 2) res *= a; return res; }
template <int P>
struct MInt {
    int x;
    MInt() : x{} {}
    MInt(i64 _x) : x{norm(_x % P)} {}
    int norm(int _x) const { if (_x < 0) _x += P; if (_x >= P) _x -= P; return _x; }
    int val() const { return x; }
    explicit operator int() const { return x; }
    MInt operator-() const { MInt res; res.x = norm(P - x); return res; }
    MInt inv() const { assert(x != 0); return power(*this, P - 2); }
    MInt &operator*=(MInt rhs) { x = (i64)x * rhs.x % P; return *this; }
    MInt &operator+=(MInt rhs) { x = norm(x + rhs.x); return *this; }
    MInt &operator-=(MInt rhs) { x = norm(x - rhs.x); return *this; }
    MInt &operator/=(MInt rhs) { return *this *= rhs.inv(); }
    friend MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; }
    friend MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; }
    friend MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; }
    friend MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; }
    friend istream &operator>>(istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; }
    friend ostream &operator<<(ostream &os, const MInt &a) { return os << a.val(); }
    friend bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
};
const int P = 998244353;
const int Q = 1000000007;
using Z = MInt<P>;
using R = MInt<Q>;
// clang-format on

struct H {
    vector<pair<Z, R>> pref;
    const Z z_hash = 324315;
    const R r_hash = 543853;
    H(string& s) {
        pref.emplace_back(0, 0);
        Z z_run = 1; R r_run = 1;
        for(int i = 0; i < (int)s.size(); i++) {
            pref.emplace_back(pref[i].first + s[i] * z_run, pref[i].second + s[i] * r_run);
            z_run *= z_hash, r_run *= r_hash;
        }
    }
    pair<Z, R> operator()(int l, int r) {
        return {(pref[r].first - pref[l - 1].first) * power(z_hash, l - 1).inv(),
                (pref[r].second - pref[l - 1].second) * power(r_hash, l - 1).inv()};
    }
};

int32_t main()
{
    int t = in;
    while(t--) {
        string s = in;
        int n = (int)s.size();
        H hash(s);
        int last_split = 1;
        int ans = 0;
        for(int i = 1; i <= n - i + 1; i++)
            if(hash(last_split, i) == hash(n - i + 1, n - last_split + 1)) last_split = i + 1, ans += (i == n - i + 1 ? 1 : 2);
        if(n % 2 == 0 && last_split != n / 2 + 1) ans++;
        cout << ans << endl;
    }
}

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