cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/AtCoder/abc284_f.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc284/tasks/abc284_f"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Sequence/RollingHash.hpp"
using namespace zawa;

#include <algorithm>
#include <iostream>
#include <string>

int main() {
    int n; std::cin >> n;
    std::string t; std::cin >> t;
    RollingHashFactory roll(1000000, 26);
    auto rt{roll.create(t)};
    std::reverse(t.begin(), t.end());
    auto tr{roll.create(t)};
    std::reverse(t.begin(), t.end());
    for (int i{} ; i <= n ; i++) {
        auto f{rt.prefix(i)}, b{rt.range(i + n, 2 * n)};
        int l{i}, r{i + n};
        auto mid{tr.range(2 * n - r, 2 * n - l)};
        if (roll.concate(f, b) == mid) {
            std::string ans{t.substr(i, n)};
            std::reverse(ans.begin(), ans.end());
            std::cout << ans << '\n' << i << '\n';
            return 0;
        }
    }
    std::cout << -1 << '\n';
}
#line 1 "Test/AtCoder/abc284_f.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc284/tasks/abc284_f"

#line 2 "Src/Template/IOSetting.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/Sequence/RollingHash.hpp"

#line 2 "Src/Number/Mersenne61ModInt.hpp"

#line 4 "Src/Number/Mersenne61ModInt.hpp"

namespace zawa {

// @reference: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
class Mersenne61ModInt {
public:
    using Value = u64;
private:
    static constexpr Value MOD{(1ull << 61) - 1}; // == MASK61
    static constexpr Value MASK30{(1ull << 30) - 1};
    static constexpr Value MASK31{(1ull << 31) - 1};
    Value v_{};
public:
    constexpr Mersenne61ModInt() {}

    static constexpr Value Mod() noexcept {
        return MOD;
    }
    static constexpr Value Modulo(const Value& v) noexcept {
        Value res{(v >> 61) + (v & MOD)};
        res = (res >= MOD ? res - MOD : res);
        return res;
    }
    static constexpr Value UnsafeMul(const Value& a, const Value& b) noexcept {
        Value fa{a >> 31}, fb{b >> 31};
        Value ba{a & MASK31}, bb{b & MASK31};
        Value mid{fa * bb + fb * ba};
        return Value{2}*fa*fb + (mid >> 30) + ((mid & MASK30) << 31) + ba*bb;
    }
    static constexpr Value Mul(const Value& a, const Value& b) noexcept {
        return Modulo(UnsafeMul(a, b));
    }
};

};
#line 5 "Src/Sequence/RollingHash.hpp"

#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <random>
#include <string>
#include <type_traits>
#include <vector>

namespace zawa {

class RollingHashFactory {
public:
    using Modulo = Mersenne61ModInt;
    using Value = Modulo::Value;
    using Size = usize;
    class Hash {
    private:
        Value hash_{};        
        Size len_{};
    public:
        Hash() {}
        Hash(Value hash, usize len) : hash_{hash}, len_{len} {}
        Value hash() const noexcept {
            return hash_;
        }
        Size len() const noexcept {
            return len_;
        }
        friend bool operator==(const Hash& lhs, const Hash& rhs) {
            return lhs.hash() == rhs.hash() and lhs.len() == rhs.len();
        }
        friend bool operator!=(const Hash& lhs, const Hash& rhs) {
            return lhs.hash() != rhs.hash() or lhs.len() != rhs.len();
        }
    };
    static constexpr Value mod{Modulo::Mod()};
private:
    std::mt19937 mt{std::random_device{}()};
    std::vector<Value> pows{};
    Value base{};

    void expand(Size len) {
        Size now{pows.size()};
        if (len + 1 <= now) return;
        pows.resize(len + 1);
        for (Size i{now} ; i < pows.size() ; i++) {
            pows[i] = Modulo::Mul(pows[i - 1], base);
        }
    }

public:
    RollingHashFactory() = default;
    RollingHashFactory(Size initLength, Value maxSigma = 127) 
        : pows(1, Value{1}), base{(mt() % (mod - maxSigma)) + maxSigma + 1} {
        pows.reserve(initLength + 1);
        expand(initLength);
    }

    class RollingHash {
    public:
        using Value = RollingHashFactory::Value;
        using Size = RollingHashFactory::Size;
        using Hash = RollingHashFactory::Hash;
    private:
        using Modulo = RollingHashFactory::Modulo;
        Size n_{};
        std::vector<Hash> prefix_{};
        std::shared_ptr<std::vector<Value>> pows_{};
    public:
        RollingHash() = default;
        RollingHash(const std::vector<Hash>& prefix, const std::vector<Value>& pows) 
            : n_{prefix.size() - 1}, prefix_{prefix}, pows_{std::make_shared<std::vector<Value>>(pows)} {}

        constexpr Size size() const noexcept {
            return n_;
        }

        Hash prefix(Size r) const {
            assert(r <= size());
            return prefix_[r];
        }

        Hash range(Size l, Size r) const {
            assert(l <= size());
            assert(l <= r);
            assert(r <= size());
            static constexpr Value positiver{4ull * Modulo::Mod()};
            return Hash{
                Modulo::Modulo(prefix_[r].hash() + positiver - Modulo::UnsafeMul(prefix_[l].hash(), (*pows_)[r - l])),
                r - l
            };
        }

        Size lcp(Size l1, Size r1, Size l2, Size r2) {
            assert(l1 <= size());
            assert(r1 <= size());
            assert(l2 <= size());
            assert(r2 <= size());
            assert(l1 <= r1);
            assert(l2 <= r2);
            Size L{}, R{std::min(r1 - l1, r2 - l2) + 1};
            while (R - L > 1) {
                Size mid{(L + R) >> 1};
                (range(l1, l1 + mid) == range(l2, l2 + mid) ? L : R) = mid;
            }
            return L;
        }
    };

    template <class RandomAccessIterator>
    RollingHash create(RandomAccessIterator first, RandomAccessIterator last) {
        static_assert(std::is_convertible_v<decltype(*first), Value>, "value must be convertible to unsigned integer");
        Size n{static_cast<Size>(std::distance(first, last))};
        expand(n);
        std::vector<Hash> roll(1);
        roll.reserve(n + 1);
        for (auto it{first} ; it != last ; it++) {
            roll.emplace_back(
                Modulo::Modulo(Modulo::UnsafeMul(roll.back().hash(), base) + *it),
                roll.back().len() + 1
            );
        }
        return RollingHash(roll, pows);
    }

    template <class T>
    RollingHash create(const std::vector<T>& a) {
        return create(a.begin(), a.end()); 
    }

    template <class T>
    Hash hash(const std::vector<T>& a) {
        static_assert(std::is_convertible_v<T, Value>, "value must be convertible to unsigned integer");
        expand(a.size());
        Value value{};
        for (const T& x : a) {
            value = Modulo::Modulo(Modulo::UnsafeMul(value, base) + x);
        }
        return Hash{value, a.size()};
    }

    RollingHash create(const std::string& s) {
        return create(s.begin(), s.end());
    }

    Hash hash(const std::string& s) {
        expand(s.size());
        Value value{};
        for (const char& c : s) {
            value = Modulo::Modulo(Modulo::UnsafeMul(value, base) + c);
        }
        return Hash{value, s.size()};
    }

    Hash concate(const Hash& lhs, const Hash& rhs) {
        return Hash{
            Modulo::Modulo(Modulo::UnsafeMul(lhs.hash(), pows[rhs.len()]) + rhs.hash()),
            lhs.len() + rhs.len()
        };
    }
};


} // namespace zawa
#line 5 "Test/AtCoder/abc284_f.test.cpp"
using namespace zawa;

#line 10 "Test/AtCoder/abc284_f.test.cpp"

int main() {
    int n; std::cin >> n;
    std::string t; std::cin >> t;
    RollingHashFactory roll(1000000, 26);
    auto rt{roll.create(t)};
    std::reverse(t.begin(), t.end());
    auto tr{roll.create(t)};
    std::reverse(t.begin(), t.end());
    for (int i{} ; i <= n ; i++) {
        auto f{rt.prefix(i)}, b{rt.range(i + n, 2 * n)};
        int l{i}, r{i + n};
        auto mid{tr.range(2 * n - r, 2 * n - l)};
        if (roll.concate(f, b) == mid) {
            std::string ans{t.substr(i, n)};
            std::reverse(ans.begin(), ans.end());
            std::cout << ans << '\n' << i << '\n';
            return 0;
        }
    }
    std::cout << -1 << '\n';
}
Back to top page