#868388 (C++17) No.2298 yukicounter

• 問題: No.2298 yukicounter
• ユーザー: nu50218
• 提出日時: 2023-05-12 21:28:55
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 289 ms / 2,000 ms
• コード長: 7,415 bytes
• コンパイル時間: 3,412 ms
• コンパイル使用メモリ: 225,548 KB
• 実行使用メモリ: 40,836 KB
• 最終ジャッジ日時: 2024-05-06 11:04:50
• 合計ジャッジ時間: 6,444 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	14 ms; 6,816 KB
testcase_01	AC	13 ms; 6,940 KB
testcase_02	AC	15 ms; 6,940 KB
testcase_03	AC	189 ms; 26,968 KB
testcase_04	AC	77 ms; 12,160 KB
testcase_05	AC	24 ms; 6,940 KB
testcase_06	AC	275 ms; 38,392 KB
testcase_07	AC	72 ms; 11,520 KB
testcase_08	AC	31 ms; 6,944 KB
testcase_09	AC	43 ms; 7,936 KB
testcase_10	AC	19 ms; 6,940 KB
testcase_11	AC	58 ms; 9,472 KB
testcase_12	AC	52 ms; 9,216 KB
testcase_13	AC	64 ms; 10,240 KB
testcase_14	AC	68 ms; 10,496 KB
testcase_15	AC	13 ms; 6,940 KB
testcase_16	AC	31 ms; 6,940 KB
testcase_17	AC	29 ms; 6,940 KB
testcase_18	AC	13 ms; 6,940 KB
testcase_19	AC	11 ms; 6,940 KB
testcase_20	AC	12 ms; 6,944 KB
testcase_21	AC	15 ms; 6,944 KB
testcase_22	AC	34 ms; 11,392 KB
testcase_23	AC	59 ms; 10,240 KB
testcase_24	AC	289 ms; 40,836 KB
testcase_25	AC	110 ms; 19,728 KB
testcase_26	AC	39 ms; 8,576 KB
testcase_27	AC	187 ms; 30,868 KB
testcase_28	AC	40 ms; 8,192 KB
testcase_29	AC	38 ms; 7,168 KB
testcase_30	AC	13 ms; 6,944 KB
testcase_31	AC	33 ms; 6,944 KB
testcase_32	AC	36 ms; 8,192 KB

ソースコード

#line 1 "main.cpp"
#ifdef LOCAL
#include <local.hpp>
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2")
#include <bits/stdc++.h>
#define debug(...) ((void)0)
#define postprocess(...) ((void)0)
#endif

#line 1 "library/string/rolling_hash.hpp"
#include <cassert>
#include <cstdint>
#include <type_traits>

#line 2 "library/misc/xorshift.hpp"

#include <bits/stdc++.h>

inline uint32_t xorshift32() {
    static uint32_t x = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

inline uint64_t xorshift64() {
    static uint64_t x = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    return x;
}
#line 6 "library/string/rolling_hash.hpp"

namespace rolling_hash {
constexpr uint64_t mod = (1ull << 61) - 1;
constexpr uint64_t primitive_root = 37;

inline uint64_t multiply(const __uint128_t& x, const __uint128_t& y) {
    // https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
    __uint128_t t = x * y;
    t = (t >> 61) + (t & mod);
    if (t >= mod) return t - mod;
    return t;
}

inline uint64_t pow_primitive_root(uint64_t k) {
    uint64_t ret = 1;
    uint64_t mul = primitive_root;
    while (k > 0) {
        if (k & 1) ret = multiply(ret, mul);
        mul = multiply(mul, mul);
        k >>= 1;
    }
    return ret;
}

inline uint64_t choose_base() {
    while (true) {
        uint64_t k = xorshift64() % (mod - 1);
        if (std::gcd(k, mod - 1) != 1) continue;

        uint64_t rk = pow_primitive_root(k);
        if (rk >= mod / 2) return rk;
    }
}

const uint64_t base0 = choose_base();
const uint64_t base1 = choose_base();

inline uint64_t pow0(uint64_t k) {
    uint64_t ret = 1;
    uint64_t mul = base0;
    while (k > 0) {
        if (k & 1) ret = multiply(ret, mul);
        mul = multiply(mul, mul);
        k >>= 1;
    }
    return ret;
}

inline uint64_t pow1(uint64_t k) {
    uint64_t ret = 1;
    uint64_t mul = base1;
    while (k > 0) {
        if (k & 1) ret = multiply(ret, mul);
        mul = multiply(mul, mul);
        k >>= 1;
    }
    return ret;
}

const uint64_t base0_inv = pow0(mod - 2);
const uint64_t base1_inv = pow1(mod - 2);

struct hash {
    uint64_t length;
    uint64_t hash0;
    uint64_t hash1;

    bool operator==(const hash& rhs) const {
        return hash0 == rhs.hash0 && hash1 == rhs.hash1 && length == rhs.length;
    }

    friend hash operator+(const hash& lhs, const hash& rhs) {
        hash ret;
        ret.length = lhs.length + rhs.length;
        ret.hash0 = multiply(lhs.hash0, pow0(rhs.length)) + rhs.hash0;
        ret.hash1 = multiply(lhs.hash1, pow1(rhs.length)) + rhs.hash1;
        if (ret.hash0 >= mod) ret.hash0 -= mod;
        if (ret.hash1 >= mod) ret.hash1 -= mod;
        return ret;
    }
};
}  // namespace rolling_hash

struct RollingHash {
    RollingHash(const std::string& s) : n(s.size()) {
        std::vector<uint64_t> v(s.size());
        for (int i = 0; i < (int)s.size(); i++) {
            v[i] = (uint64_t)s[i];
        }
        init(v);
    }

    template <typename T>
    RollingHash(const std::vector<T>& s) : n(s.size()) {
        static_assert(std::is_integral_v<T>, "T must be an integer type");
        std::vector<uint64_t> v(s.size());
        for (int i = 0; i < (int)s.size(); i++) {
            v[i] = (uint64_t)s[i];
        }
        init(v);
    }

    int size() {
        return n;
    }

    // returns hash value for [l, r).
    // Complexity: O(1)
    rolling_hash::hash query(int l, int r) {
        assert(0 <= l);
        assert(l <= r);
        assert(r <= n);

        rolling_hash::hash ret;

        if (r == 0) {
            ret.length = r;
            ret.hash0 = 0;
            ret.hash1 = 0;
            return ret;
        }

        if (l == 0) {
            ret.length = r;
            ret.hash0 = accumulated0[r - 1];
            ret.hash1 = accumulated1[r - 1];
            return ret;
        }

        ret.length = r - l;

        ret.hash0 = accumulated0[r - 1] - accumulated0[l - 1] + rolling_hash::mod;
        if (ret.hash0 >= rolling_hash::mod) ret.hash0 -= rolling_hash::mod;
        ret.hash0 = rolling_hash::multiply(ret.hash0, inv0[l]);

        ret.hash1 = accumulated1[r - 1] - accumulated1[l - 1] + rolling_hash::mod;
        if (ret.hash1 >= rolling_hash::mod) ret.hash1 -= rolling_hash::mod;
        ret.hash1 = rolling_hash::multiply(ret.hash1, inv1[l]);

        return ret;
    }

    // returns the length of Longest Common Prefix
    // between suffixes starting from l1, l2,
    // that is, maximum L such that [l1, l1 + L) == [l2, l2 + L).
    // Complexity: O(log N)
    int lcp(int l1, int l2) {
        int imin = 0;
        int imax = n - std::max(l1, l2) + 1;

        while (imax - imin > 1) {
            int imid = (imin + imax) / 2;

            auto h1 = query(l1, l1 + imid);
            auto h2 = query(l2, l2 + imid);

            (h1 == h2 ? imin : imax) = imid;
        }

        return imin;
    }

   private:
    int n;
    std::vector<uint64_t> accumulated0;
    std::vector<uint64_t> accumulated1;
    std::vector<uint64_t> inv0;
    std::vector<uint64_t> inv1;

    void init(const std::vector<uint64_t>& v) {
        accumulated0.resize(n);
        accumulated1.resize(n);

        uint64_t base0 = 1;
        uint64_t base1 = 1;

        for (int i = 0; i < (int)v.size(); i++) {
            accumulated0[i] = rolling_hash::multiply(v[i], base0);
            accumulated1[i] = rolling_hash::multiply(v[i], base1);

            base0 = rolling_hash::multiply(base0, rolling_hash::base0);
            base1 = rolling_hash::multiply(base1, rolling_hash::base1);
        }

        for (int i = 1; i < (int)v.size(); i++) {
            accumulated0[i] += accumulated0[i - 1];
            if (accumulated0[i] >= rolling_hash::mod) accumulated0[i] -= rolling_hash::mod;
            accumulated1[i] += accumulated1[i - 1];
            if (accumulated1[i] >= rolling_hash::mod) accumulated1[i] -= rolling_hash::mod;
        }

        inv0.resize(n);
        inv1.resize(n);

        inv0[0] = 1;
        inv1[0] = 1;

        for (int i = 0; i + 1 < n; i++) {
            inv0[i + 1] = rolling_hash::multiply(inv0[i], rolling_hash::base0_inv);
            inv1[i + 1] = rolling_hash::multiply(inv1[i], rolling_hash::base1_inv);
        }
    }
};
#line 12 "main.cpp"

using namespace std;
using ll = long long;
using ld = long double;

void solve([[maybe_unused]] int test) {
    string S;
    cin >> S;

    int N = S.size();

    RollingHash rh(S);

    const auto pattern = RollingHash("yukicoder").query(0, 9);

    int imin = 0;
    int imax = 1000000;

    while (imax - imin > 1) {
        int imid = (imin + imax) / 2;

        auto hash = pattern;
        for (int i = 1; i < imid; i++) {
            hash = hash + pattern;
        }

        bool ok = false;

        int len = imid * 9;
        for (int i = 0; i + len <= N; i++) {
            if (rh.query(i, i + len) == hash) {
                ok = true;
                break;
            }
        }

        (ok ? imin : imax) = imid;
    }

    cout << imin << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) {
        solve(i);
    }

    postprocess();
}