Submission #1095029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095029		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	291 ms	35908 KiB

palindromic

#include <bits/stdc++.h>
// #ifndef ONLINE_JUDGE
// #include "/Users/quocbaonguyentran/Documents/VOI25/template/debug.cpp"
// #else
// #define debug(...) ;
// #endif
using namespace std;
#define endl "\n"
#define ll long long
#define ull uint64_t
#define uint uint32_t
const int N = 1e6;
const ull mod = (1ull << 61) - 1;
const ull seed = chrono::system_clock::now().time_since_epoch().count();
const ull base = mt19937_64(seed)() % (mod / 3) + (mod / 3);
ull Pow[N + 5];
ll modmul(ull a, ull b)
{
    ull l1 = (uint)a;
    ull h1 = a >> 32;
    ull l2 = (uint)b;
    ull h2 = b >> 32;
    ull l = l1 * l2;
    ull m = l1 * h2 + l2 * h1;
    ull h = h1 * h2;
    ull res = (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
    res = (res & mod) + (res >> 61);
    res = (res & mod) + (res >> 61);
    return res - 1;
}
void init()
{
    Pow[0] = 1;
    for (int i = 1; i <= N; i++)
    {
        Pow[i] = modmul(Pow[i - 1], base);
    }
}
struct Hashing
{
    vector<ll> pre, suf;
    Hashing() {}
    template <typename T>
    Hashing(const vector<T> &a)
    {
        if (Pow[0] == 0)
            init();
        int n = a.size();
        pre = suf = vector<ll>(n + 5, 0);
        for (int i = 1; i <= n; i++)
        {
            pre[i] = modmul(pre[i - 1], base) + a[i - 1] + 977;
            if (pre[i] >= mod)
                pre[i] -= mod;
        }
        for (int i = n; i >= 1; i--)
        {
            suf[i] = modmul(suf[i + 1], base) + a[i - 1] + 977;
            if (suf[i] >= mod)
                suf[i] -= mod;
        }
    }
    Hashing(const char *str)
        : Hashing(vector<char>(str, str + strlen(str))) {}
    Hashing(const string &str)
        : Hashing(vector<char>(str.begin(), str.end())) {}

    ull get_hash(int l, int r)
    {
        ll h = pre[r] - modmul(Pow[r - l + 1], pre[l - 1]);
        return h < 0 ? h + mod : h;
    }
    ull rev_hash(int l, int r)
    {
        ll h = suf[l] - modmul(Pow[r - l + 1], suf[r + 1]);
        return h < 0 ? h + mod : h;
    }
};
int t;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    while (t--)
    {
        string s;
        cin >> s;
        Hashing t(s);
        int n = s.size();
        int l = 1, r = n;
        int le = 1, ri = n;
        int dem = 0;
        while (l < r)
        {
            // debug(le, l, ri, r);
            if (t.get_hash(le, l) == t.get_hash(r, ri))
            {
                dem++;
                le = l + 1;
                ri = r - 1;
            }
            l++;
            r--;
        }
        // debug(le, l, ri, r);
        dem *= 2;
        if (le <= ri) dem++;
        cout << dem << endl;
    }
}
/*
4
bonobo
deleted
racecar
racecars
*/

Compilation message (stderr)

palindromic.cpp: In instantiation of 'Hashing::Hashing(const std::vector<_Tp>&) [with T = char]':
palindromic.cpp:64:55:   required from here
palindromic.cpp:53:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
   53 |             if (pre[i] >= mod)
palindromic.cpp:59:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
   59 |             if (suf[i] >= mod)

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