Submission #396513

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
396513	2021-04-30T06:01:51 Z	KoD	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	266 ms	708 KB

necklace

#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept {
            return itr != other.itr;
        }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept
        : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

template <class T> bool setmax(T& lhs, const T& rhs) {
    if (lhs < rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}

template <class T> using Vec = std::vector<T>;

Vec<usize> knuth_morris_pratt(const std::string& S) {
    const auto N = S.size();
    Vec<usize> ret(N + 1);
    ret[0] = -1;
    usize j = -1;
    for (const auto i : rep(0, N)) {
        while ((~j) and S[i] != S[j]) {
            j = ret[j];
        }
        j += 1;
        ret[i + 1] = j;
    }
    ret[0] = 0;
    return ret;
}

std::tuple<usize, usize, usize> solve(const std::string& S,
                                      const std::string& T,
                                      const std::string& revT) {
    const auto N = S.size();
    const auto M = T.size();
    std::tuple<usize, usize, usize> ret(0, 0, 0);
    for (const auto split : rep(0, N + 1)) {
        const auto s1 = S.substr(0, split);
        const auto s2 = S.substr(split, N - split);
        const auto A = knuth_morris_pratt(std::string(s1.rbegin(), s1.rend()) +
                                          '$' + revT);
        const auto B = knuth_morris_pratt(s2 + '$' + T);
        for (const auto k : rep(0, M + 1)) {
            const auto f = A[A.size() - k - 1];
            const auto b = B[s2.size() + k + 1];
            setmax(ret, std::make_tuple(b + f, split - f, k - b));
        }
    }
    return ret;
}

void BOI19_Necklace_main() {
    std::string S, T;
    std::cin >> S >> T;
    const auto revT = std::string(T.rbegin(), T.rend());
    const auto [a1, i1, j1] = solve(S, T, revT);
    const auto [a2, i2, j2] = solve(S, revT, T);
    if (a1 > a2) {
        std::cout << a1 << '\n';
        std::cout << i1 << ' ' << j1 << '\n';
    } else {
        std::cout << a2 << '\n';
        std::cout << i2 << ' ' << T.size() - (a2 + j2) << '\n';
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    BOI19_Necklace_main();
    return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	249 ms	548 KB	Output is correct
2	Correct	212 ms	480 KB	Output is correct
3	Correct	240 ms	604 KB	Output is correct
4	Correct	180 ms	584 KB	Output is correct
5	Correct	236 ms	460 KB	Output is correct
6	Correct	266 ms	484 KB	Output is correct
7	Correct	235 ms	464 KB	Output is correct
8	Correct	240 ms	480 KB	Output is correct
9	Correct	237 ms	708 KB	Output is correct