oj.uz

Submission #1095029

# Submission time Handle Problem Language Result Execution time Memory
1095029 2024-10-01T07:34:42 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 291 ms 35908 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8024 KB Output is correct
2 Correct 9 ms 8284 KB Output is correct
3 Correct 8 ms 8240 KB Output is correct
4 Correct 8 ms 8284 KB Output is correct
5 Correct 7 ms 8184 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8024 KB Output is correct
2 Correct 9 ms 8284 KB Output is correct
3 Correct 8 ms 8240 KB Output is correct
4 Correct 8 ms 8284 KB Output is correct
5 Correct 7 ms 8184 KB Output is correct
6 Correct 8 ms 8284 KB Output is correct
7 Correct 7 ms 8284 KB Output is correct
8 Correct 8 ms 8284 KB Output is correct
9 Correct 8 ms 8284 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8024 KB Output is correct
2 Correct 9 ms 8284 KB Output is correct
3 Correct 8 ms 8240 KB Output is correct
4 Correct 8 ms 8284 KB Output is correct
5 Correct 7 ms 8184 KB Output is correct
6 Correct 8 ms 8284 KB Output is correct
7 Correct 7 ms 8284 KB Output is correct
8 Correct 8 ms 8284 KB Output is correct
9 Correct 8 ms 8284 KB Output is correct
10 Correct 11 ms 8824 KB Output is correct
11 Correct 10 ms 8480 KB Output is correct
12 Correct 12 ms 8528 KB Output is correct
13 Correct 9 ms 8488 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8024 KB Output is correct
2 Correct 9 ms 8284 KB Output is correct
3 Correct 8 ms 8240 KB Output is correct
4 Correct 8 ms 8284 KB Output is correct
5 Correct 7 ms 8184 KB Output is correct
6 Correct 8 ms 8284 KB Output is correct
7 Correct 7 ms 8284 KB Output is correct
8 Correct 8 ms 8284 KB Output is correct
9 Correct 8 ms 8284 KB Output is correct
10 Correct 11 ms 8824 KB Output is correct
11 Correct 10 ms 8480 KB Output is correct
12 Correct 12 ms 8528 KB Output is correct
13 Correct 9 ms 8488 KB Output is correct
14 Correct 291 ms 35908 KB Output is correct
15 Correct 152 ms 30300 KB Output is correct
16 Correct 285 ms 34044 KB Output is correct
17 Correct 147 ms 23128 KB Output is correct