Submission #1133053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133053		shoeib	Palindromic Partitions (CEOI17_palindromic)	C++20	60 / 100	10095 ms	65232 KiB

palindromic

// Author: Muhammed Khaled Shoeib

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
//....................................................
// struct to speed-up the unordered data structures like map/set.
struct hash_function // unordered + modified hash >> ordered
{   static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM); } };
//....................................................
template < typename T, typename Compare = less < T > > // O(logn)
using ordered_set = tree < T, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;
// less_equal:    asc.  not_unique, st.order_of_key(k) --> no. of items < k,  less: unique
// greater_equal: desc. not_unique, st.order_of_key(k) --> no. of items > k,  greater: unique
// *st.find_by_order(k) --> st[k] (Zero-indexed)
// less_equal (u can't erase here!) == multi-set
template < typename T > using maxpq = priority_queue < T >;
template < typename T > using minpq = priority_queue < T, vector< T >, greater< T > >;
//....................................................
#define     boost                  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define     precision(a)           cout << fixed << setprecision(a)
#define     alo                    cout << "alooooooooooo!" << endl
#define     YES                    cout << "YES" << endl
#define     Yes                    cout << "Yes" << endl
#define     yes                    cout << "yes" << endl
#define     NO                     cout << "NO" << endl
#define     No                     cout << "No" << endl
#define     no                     cout << "no" << endl
#define     ne                     cout << -1 << endl
#define     endl                   "\n"
#define     mem(mat, val)          memset(mat, val, sizeof(mat))
#define     ones(x)                __builtin_popcountll(x)
#define     msb(x)                 63ll - __builtin_clzll(x)
#define     lsb(x)                 __builtin_ffsll(x) - 1ll
//....................................................
#define     all(x)                 x.begin(), x.end()
#define     rall(x)                x.rbegin(),x.rend()
#define ceil_(a, b) (((ll)(a) + (ll)(b - 1)) / (ll)(b)) // up
#define floor_(a, b) (a / b) // down
#define round_(a, b) ((a + (b / 2ll)) / b) // nearest
//....................................................
// using ll  = int;                                                                     // take care of this shit!
using ll  = long long;
using i64 = long long; using i32 = int;
using ld  = long double;  using ull = unsigned long long;  using lli = long long int;
//......................................................
ll gcd_(ll x, ll y) { return y ? gcd_(y, x % y) : x; } // O(log(min(x, y)))
ll lcm_(ll a, ll b) { ll g = gcd_(a, b); return (a * b) / g; }
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//......................................................
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dx_diag[4] = { 1, 1, -1, -1 }, dy_diag[4] = { 1, -1, -1, 1 };
int dx_all[8] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy_all[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dx_knight[8] = {2, 2, 1, 1, -2, -2, -1, -1}, dy_knight[8] = {1, -1, 2, -2, 1, -1, 2, -2};
const ld  pi  = 3.141592653589793238462643383279; // acos(-1)
const ld eps = 1e-9;
const ll inf = (ll)INT32_MAX; // 2e9
const ll oo = (ll)1e15;       // 1e15 (may cause OF in DP, Binary Search, ...)
const ll OO = (ll)INT64_MAX;  // 9e18
const ll mod  = (ll)1e9 + 7; // 1e9 + 7, 998244353
//..................................................... // string(len, char);
/*
 * think twice, code once.
 * think of different approaches to tackle a problem, write them down.
 * think of different views of the problem, don't look from only one side.
 * don't get stuck in one approach/problem.
 * common mistakes: line 48, overflow (sum of many numbers), corner cases, over/under count, infinite loops,
 * TLE, MLE (int instead of ll, using memset, Recursive DP, ...), RTE (out of bounds indexing), ....
 */
///____________________________________________ Shoeib __________________________________________________________


/*              Prefix String Single Hashing               */
// pre-processing in O(N), querying (comparing different ranges) in O(1)
// adjust base (29, 31, 37, 41, 137, 277), mod (127657753, 987654319, 998244353, 1e9 + 7, 1e9 + 9)
// smaller hash value doesn't mean smaller lexicographically.

// ....................

const ll N = (ll)1e6 + 6, base1 = 31, mod1 = (ll)127657753;
const char _ref = 'a' - 1ll; // 'a', 'A'

// ....................

// Modular(Binary) Exponentiation: Quick calculation of ((x^n) mod m) in O(log(n))
ll mod_exp(ll x, ll n, ll m = mod)
{
    ll res = 1;
    while(n)
    {
        if (n % 2) res = (((res % m) * (x % m)) % m);
        x = (((x % m) * (x % m)) % m);
        n /= 2;
    }
    return res;
}

// Modular Arithmetic operations
ll mod_mul(ll x , ll y, ll m = mod) { return (((x % m) * (y % m)) % m); }
ll mod_inv(ll x, ll m = mod){ return mod_exp(x , m - 2, m); } // Fermat’s little theorem (m is a prime number)
ll mod_div(ll x, ll y, ll m = mod){ return mod_mul(x, mod_inv(y, m), m); }
ll mod_add(ll x, ll y, ll m = mod) { ll z = (x % m) + (y % m); z %= m; return z; }
ll mod_sub(ll x, ll y, ll m = mod) { ll z = (x % m) - (y % m); while(z < 0) z += m; z %= m; return z; }

// ....................

ll inv1;
vector < ll > pow1(N);
void pre_process()
{
    inv1 = mod_inv(base1, mod1);
    pow1[0] = 1;
    for(ll i = 1; i < N; i++)
        pow1[i] = mod_mul(pow1[i - 1], base1, mod1);
}

struct _Hash_pre
{
    ll n;
    string s;
    vector < ll > pre1;

    _Hash_pre(const string _s) : s(_s), n((ll)_s.size()) { _generate_pre(); }
    _Hash_pre() : s(""), n(0) {  }

    void _generate_pre()
    {
        pre1.assign(N, 0);
        for (ll i = 0; i < n; i++) // (n - 1) ... 2 1 0
        {
            ll digit = (ll)(s[i] - _ref);
            if(i) pre1[i] = mod_mul(pre1[i - 1], base1, mod1);
            pre1[i] = mod_add(pre1[i], digit, mod1);
        }
    }

    ll _get_range(ll l, ll r)
    {
        ll len = (r - l + 1);
        ll val1 = pre1[r];
        if(l > 0) val1 = mod_sub(val1, mod_mul(pre1[l - 1], pow1[len], mod1), mod1);
        return val1;
    }

};

// ....................

string s;
ll n;

_Hash_pre hash1;

ll tt = 1;
ll dp[N], vis[N];

ll slv(ll l1)
{
    ll r2 = (n - 1) - l1;
    if(l1 > r2) return 0;

    ll &ret = dp[l1];
    if(vis[l1] == tt) return ret;
    vis[l1] = tt;
    ret = 1;

    ll r1 = l1, l2 = r2;
    while(r1 < l2)
    {
        if(hash1._get_range(l1, r1) == hash1._get_range(l2, r2))
        {
            ret = max(ret, 2 + slv(r1 + 1));
        }
        r1++; l2--;
    }


    return ret;
}


void solve()
{

    cin >> s;
    n = (ll)s.size();

    hash1 = _Hash_pre(s);

    cout << slv(0) << endl;
    tt++;





    return;
}



signed main()
{
    pre_process();

    boost;

//    freopen("assessment.in", "r", stdin);
//    freopen("output.txt", "w", stdout);

//    precision(15);

    i32 _ = 1; cin >> _;
//    cout.flush();
    while(_--) solve();
    return 0;
}

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