제출 #1095027

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1095027		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	컴파일 에러	0 ms	0 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
*/

컴파일 시 표준 에러 (stderr) 메시지

palindromic.cpp:3:10: fatal error: /Users/quocbaonguyentran/Documents/VOI25/template/debug.cpp: No such file or directory
    3 | #include "/Users/quocbaonguyentran/Documents/VOI25/template/debug.cpp"
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.