oj.uz

Submission #835800

# Submission time Handle Problem Language Result Execution time Memory
835800 2023-08-23T20:23:13 Z elkernos Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 4721 ms 27336 KB 
// 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 += 2;
        if(n % 2 == 0 && last_split != n / 2 + 1) ans++;
        if(n % 2 == 1 && last_split != (n + 1) / 2 + 1) ans++;
        cout << ans << endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 42 ms 644 KB Output is correct
11 Correct 23 ms 600 KB Output is correct
12 Correct 44 ms 632 KB Output is correct
13 Correct 36 ms 604 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 42 ms 644 KB Output is correct
11 Correct 23 ms 600 KB Output is correct
12 Correct 44 ms 632 KB Output is correct
13 Correct 36 ms 604 KB Output is correct
14 Correct 4721 ms 27336 KB Output is correct
15 Correct 2338 ms 22332 KB Output is correct
16 Correct 4634 ms 26424 KB Output is correct
17 Correct 2610 ms 18752 KB Output is correct