Submission #40025099
Source Code Expand
#ifndef _CPPEXPANDER_9ED4DBBE6D94F8C5
#define _CPPEXPANDER_9ED4DBBE6D94F8C5
#include <atcoder/all>
#ifndef _CPPEXPANDER_BEA235947CFE79B4
#define _CPPEXPANDER_BEA235947CFE79B4
#if __has_include(<bits/stdc++.h>)
#include <bits/stdc++.h>
#else
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#endif
#ifndef _CPPEXPANDER_6F29225E071A593C
#define _CPPEXPANDER_6F29225E071A593C
#include <tuple>
#include <utility>
#include <vector>
#ifndef _CPPEXPANDER_92A4F221BE37F8A6
#define _CPPEXPANDER_92A4F221BE37F8A6
#include <iterator>
#include <tuple>
#include <type_traits>
#include <utility>
namespace mihatsu::_internal {
// ---- constant mappings ----
template <typename>
constexpr inline bool false_v = false;
template <typename>
constexpr inline bool true_v = true;
// ---- type traits ----
template <typename, typename = void>
struct is_maplike : std::false_type {};
template <typename T>
struct is_maplike<T, std::void_t<typename T::mapped_type>> : std::true_type {};
template <typename T>
constexpr inline bool is_maplike_v = is_maplike<T>::value;
template <typename, typename = void>
struct is_setlike : std::false_type {};
template <typename T>
struct is_setlike<T, std::enable_if_t<std::is_same_v<typename T::key_type, typename T::value_type>>> : std::true_type {};
template <typename T>
constexpr inline bool is_setlike_v = is_setlike<T>::value;
template <typename, typename = void>
struct is_container : std::false_type {};
template <typename T>
struct is_container<T, std::void_t<decltype(std::begin(std::declval<T>()))>> : std::true_type {};
template <typename T>
constexpr inline bool is_container_v = is_container<T>::value;
template <typename, typename = void>
struct is_pairlike : std::false_type {};
template <typename T>
struct is_pairlike<T, std::void_t<typename T::first_type, typename T::second_type>> : std::true_type {};
template <typename T>
constexpr inline bool is_pairlike_v = is_pairlike<T>::value;
template <std::nullptr_t = nullptr>
struct is_subscriptable_impl {
template <class T, class U>
constexpr auto operator()(T&& a, U&& b) -> decltype(a[b], std::true_type{}) {
return std::true_type{};
}
constexpr auto operator()(...) -> std::false_type {
return std::false_type{};
}
};
template <class T, class U>
constexpr inline bool is_subscriptable_v = std::invoke_result_t<is_subscriptable_impl<>, T, U>::value;
// ---- utilities ----
template <typename T, std::size_t N>
struct arraylike_tuple {
template <typename>
struct impl {};
template <std::size_t... I>
struct impl<std::index_sequence<I...>> {
template <std::size_t>
using T_ = T;
using type = std::tuple<T_<I>...>;
};
using type = typename impl<std::make_index_sequence<N>>::type;
};
template <typename T, std::size_t N>
using arraylike_tuple_t = typename arraylike_tuple<T, N>::type;
} // namespace mihatsu::_internal
#endif
namespace mihatsu {
namespace _internal {
template <typename T, std::size_t N>
struct nested_vector {
using type = std::vector<typename nested_vector<T, N - 1>::type>;
};
template <typename T>
struct nested_vector<T, 0> {
using type = T;
};
template <typename T, std::size_t N>
using nested_vector_t = typename nested_vector<T, N>::type;
} // namespace _internal
template <typename T, std::size_t dimension>
class MultiDimensionalVector : public _internal::nested_vector_t<T, dimension> {
static_assert(dimension > 0, "dimension of MultiDimensionalVector must be greater than 0");
using Vector = _internal::nested_vector_t<T, dimension>;
using Size = _internal::arraylike_tuple_t<std::size_t, dimension>;
template <std::size_t i>
constexpr void init(_internal::nested_vector_t<T, dimension - i>& vector, const Size& size) {
vector.resize(std::get<i>(size));
if constexpr (i + 1 < dimension) {
for (auto&& v : vector) init<i + 1>(v, size);
}
}
template <std::size_t i>
constexpr void init(_internal::nested_vector_t<T, dimension - i>& vector, const Size& size, const T& initializer) {
const std::size_t n = std::get<i>(size);
if constexpr (i + 1 < dimension) {
vector.resize(n);
for (auto&& v : vector) init<i + 1>(v, size, initializer);
} else {
vector.reserve(n);
for (std::size_t p = 0; p < n; ++p) vector.emplace_back(initializer);
}
}
public:
using Vector::Vector;
constexpr inline MultiDimensionalVector(const Vector& vector)
: Vector{vector} {}
constexpr inline MultiDimensionalVector(Vector&& vector)
: Vector{std::forward<Vector>(vector)} {}
constexpr inline MultiDimensionalVector(const Size& size) {
init<0>(*this, size);
};
constexpr inline MultiDimensionalVector(const Size& size, const T& initializer) {
init<0>(*this, size, initializer);
};
};
template <typename T>
MultiDimensionalVector(const _internal::arraylike_tuple_t<std::size_t, 0>&, const T&) -> MultiDimensionalVector<T, 0>;
template <typename T>
MultiDimensionalVector(const _internal::arraylike_tuple_t<std::size_t, 1>&, const T&) -> MultiDimensionalVector<T, 1>;
template <typename T>
MultiDimensionalVector(const _internal::arraylike_tuple_t<std::size_t, 2>&, const T&) -> MultiDimensionalVector<T, 2>;
template <typename T>
MultiDimensionalVector(const _internal::arraylike_tuple_t<std::size_t, 3>&, const T&) -> MultiDimensionalVector<T, 3>;
template <typename T>
MultiDimensionalVector(const _internal::arraylike_tuple_t<std::size_t, 4>&, const T&) -> MultiDimensionalVector<T, 4>;
template <typename T>
MultiDimensionalVector(const _internal::arraylike_tuple_t<std::size_t, 5>&, const T&) -> MultiDimensionalVector<T, 5>;
template <typename T>
MultiDimensionalVector(const _internal::arraylike_tuple_t<std::size_t, 6>&, const T&) -> MultiDimensionalVector<T, 6>;
template <typename T>
MultiDimensionalVector(const _internal::arraylike_tuple_t<std::size_t, 7>&, const T&) -> MultiDimensionalVector<T, 7>;
template <typename T>
MultiDimensionalVector(const _internal::arraylike_tuple_t<std::size_t, 8>&, const T&) -> MultiDimensionalVector<T, 8>;
template <typename T>
MultiDimensionalVector(const _internal::arraylike_tuple_t<std::size_t, 9>&, const T&) -> MultiDimensionalVector<T, 9>;
} // namespace mihatsu
#endif
#ifndef _CPPEXPANDER_257029B4D8B280D0
#define _CPPEXPANDER_257029B4D8B280D0
#include <sstream>
#include <string>
namespace mihatsu {
template <class charT, class traits = std::char_traits<charT>, class Allocator = std::allocator<charT>>
class constructible_string : public std::basic_string<charT, traits, Allocator> {
template <class T>
inline static std::basic_string<charT, traits, Allocator> init(const T& val) {
std::basic_ostringstream<charT, traits, Allocator> ss;
ss << val;
return ss.str();
}
public:
template <class T>
inline constructible_string(const T& val)
: std::basic_string<charT, traits, Allocator>{init(val)} {}
};
} // namespace mihatsu
#endif
#ifndef _CPPEXPANDER_0BFEC84B04BA4ABC
#define _CPPEXPANDER_0BFEC84B04BA4ABC
#include <algorithm>
#include <array>
#include <deque>
#include <forward_list>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <set>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#ifndef _CPPEXPANDER_52B234832A8A3B96
#define _CPPEXPANDER_52B234832A8A3B96
#include <functional>
#include <type_traits>
namespace mihatsu::_internal {
// 仮実装（TODO: 任意引数長に対応する）
struct {
template <class Fn>
inline constexpr auto operator()(Fn&& fn) {
return std::invoke(std::forward<Fn>(fn));
}
template <class Fn, class T1>
inline constexpr auto operator()(Fn&& fn, T1&& t1) {
if constexpr (std::is_invocable_v<Fn, T1>) {
return std::invoke(std::forward<Fn>(fn), std::forward<T1>(t1));
} else {
return this->operator()(std::forward<Fn>(fn));
}
}
template <class Fn, class T1, class T2>
inline constexpr auto operator()(Fn&& fn, T1&& t1, T2&& t2) {
if constexpr (std::is_invocable_v<Fn, T1, T2>) {
return std::invoke(std::forward<Fn>(fn), std::forward<T1>(t1), std::forward<T2>(t2));
} else {
return this->operator()(std::forward<Fn>(fn), std::forward<T1>(t1));
}
}
template <class Fn, class T1, class T2, class T3>
inline constexpr auto operator()(Fn&& fn, T1&& t1, T2&& t2, T3&& t3) {
if constexpr (std::is_invocable_v<Fn, T1, T2, T3>) {
return std::invoke(std::forward<Fn>(fn), std::forward<T1>(t1), std::forward<T2>(t2), std::forward<T3>(t3));
} else {
return this->operator()(std::forward<Fn>(fn), std::forward<T1>(t1), std::forward<T2>(t2));
}
}
template <class Fn, class T1, class T2, class T3, class T4>
inline constexpr auto operator()(Fn&& fn, T1&& t1, T2&& t2, T3&& t3, T4&& t4) {
if constexpr (std::is_invocable_v<Fn, T1, T2, T3, T4>) {
return std::invoke(std::forward<Fn>(fn), std::forward<T1>(t1), std::forward<T2>(t2), std::forward<T3>(t3), std::forward<T4>(t4));
} else {
return this->operator()(std::forward<Fn>(fn), std::forward<T1>(t1), std::forward<T2>(t2), std::forward<T3>(t3));
}
}
} redundant_invoke;
template <class Fn, class... Args>
constexpr inline bool is_redundant_invocable_v = std::is_invocable_v<decltype(redundant_invoke), Fn, Args...>;
template <class Fn, class... Args>
using redundant_invoke_result_t = typename std::invoke_result_t<decltype(redundant_invoke), Fn, Args...>;
} // namespace mihatsu::_internal
#endif
namespace mihatsu {
namespace _internal {
using signed_size_t = std::make_signed_t<std::size_t>;
template <typename T, typename = void>
struct container_selector {
using set = typename std::set<T>;
using multiset = typename std::multiset<T>;
template <typename U>
using map = typename std::map<T, U>;
template <typename U>
using multimap = std::multimap<T, U>;
};
template <typename T>
struct container_selector<T, std::void_t<decltype(std::hash<T>())>> {
using set = typename std::unordered_set<T>;
using multiset = typename std::unordered_multiset<T>;
template <typename U>
using map = typename std::unordered_map<T, U>;
template <typename U>
using multimap = std::unordered_multimap<T, U>;
};
namespace container_helper_base {
template <std::nullptr_t = nullptr>
struct container_invoke_t {
template <typename Fn, class First, class... Args>
inline auto operator()(Fn&& fn, First&& first, Args&&... args) {
if constexpr (is_subscriptable_v<Fn, First>) {
return std::forward<Fn>(fn)[std::forward<First>(first)];
} else {
return redundant_invoke(std::forward<Fn>(fn), std::forward<First>(first), std::forward<Args>(args)...);
}
}
};
inline container_invoke_t container_invoke;
template <typename Fn, class First, class... Args>
using container_invoke_result_t = typename std::invoke_result_t<decltype(container_invoke), Fn, First, Args...>;
template <typename Container, bool is_const>
struct base {
static_assert(!std::is_const_v<Container>, "parameter 'Container' cannot be const (use is_const=true instead)");
protected:
using _Container = typename std::conditional_t<is_const, const Container, Container>;
public:
_Container& container;
inline base(_Container& container)
: container(container) {}
inline signed_size_t size() const {
return std::size(container);
};
inline void reserve(std::size_t) {}
static constexpr bool subscriptable = false;
using value_type = typename _Container::value_type;
template <typename Iterator>
inline value_type get_value(Iterator it) const {
return *it;
}
template <typename Iterator, typename Value, std::enable_if_t<true_v<Value> && !is_const>* = nullptr>
inline void set_value(Iterator it, Value&& val) {
*it = std::forward<Value>(val);
}
static constexpr bool value_settable = !is_const;
using iterated_type = typename std::remove_reference_t<decltype(*std::begin(container))>;
template <typename Fn>
using invoke_result_t = container_invoke_result_t<Fn, value_type>;
template <typename Fn, typename Iterator>
inline auto invoke(Fn&& fn, Iterator it) {
return container_invoke(fn, *it);
}
template <typename PositionIterator, typename Value, std::enable_if_t<true_v<Value> && !is_const>* = nullptr>
inline void insert(PositionIterator, Value&& val) {
// PositionIterator is not read except for map
container.push_back(std::forward<Value>(val));
}
template <typename U>
using change_value_type = typename std::vector<U>;
};
template <typename RandomAccessContainer, bool is_const>
struct random_access : base<RandomAccessContainer, is_const> {
using base<RandomAccessContainer, is_const>::base;
static constexpr bool subscriptable = true;
using key_type = signed_size_t;
template <typename Iterator>
inline key_type get_key(Iterator it) const {
return it - std::begin(this->container);
}
using typename base<RandomAccessContainer, is_const>::value_type;
template <typename Fn>
using invoke_result_t = container_invoke_result_t<Fn, value_type, key_type>;
template <typename Fn, typename Iterator>
inline auto invoke(Fn&& fn, Iterator it) {
return container_invoke(fn, *it, static_cast<signed_size_t>(it - std::begin(this->container)));
}
};
template <typename Set, bool is_const>
struct set : base<Set, is_const> {
using base<Set, is_const>::base;
static constexpr bool value_settable = false;
template <typename PositionIterator, typename Value, std::enable_if_t<true_v<Value> && !is_const>* = nullptr>
inline void insert(PositionIterator, Value&& val) {
this->container.insert(std::forward<Value>(val));
}
};
template <typename Map, bool is_const>
struct map : base<Map, is_const> {
using base<Map, is_const>::base;
static constexpr bool subscriptable = true;
using key_type = typename Map::key_type;
template <typename Iterator>
inline key_type get_key(Iterator it) const {
return it->first;
}
using value_type = typename Map::mapped_type;
template <typename Iterator>
inline value_type get_value(Iterator it) const {
return it->second;
}
template <typename Iterator, typename Value, std::enable_if_t<true_v<Value> && !is_const>* = nullptr>
inline void set_value(Iterator it, Value&& val) {
it->second = std::forward<Value>(val);
}
template <typename Fn>
using invoke_result_t = container_invoke_result_t<Fn, value_type, key_type>;
template <typename Fn, typename Iterator>
inline auto invoke(Fn&& fn, Iterator it) {
return container_invoke(fn, it->second, it->first);
}
template <typename PositionIterator, typename Value, std::enable_if_t<true_v<Value> && !is_const>* = nullptr>
inline void insert(PositionIterator pos, Value&& val) {
this->container.emplace(pos->first, std::forward<Value>(val));
}
};
} // namespace container_helper_base
template <typename Container, bool is_const>
struct container_helper : container_helper_base::base<Container, is_const> {
using container_helper_base::base<Container, is_const>::base;
};
template <typename Container>
container_helper(Container&) -> container_helper<Container, false>;
template <typename Container>
container_helper(const Container&) -> container_helper<Container, true>;
template <class T, class Allocator, bool is_const>
struct container_helper<std::vector<T, Allocator>, is_const> : container_helper_base::random_access<std::vector<T, Allocator>, is_const> {
using container_helper_base::random_access<std::vector<T, Allocator>, is_const>::random_access;
inline void reserve(std::size_t n) {
this->container.reserve(n);
}
using iterated_type = T;
};
template <class charT, class traits, class Allocator, bool is_const>
struct container_helper<std::basic_string<charT, traits, Allocator>, is_const> : container_helper_base::random_access<std::basic_string<charT, traits, Allocator>, is_const> {
using container_helper_base::random_access<std::basic_string<charT, traits, Allocator>, is_const>::random_access;
using iterated_type = charT;
template <typename U>
using change_value_type = typename std::conditional_t<std::is_same_v<U, charT>, std::basic_string<charT>, std::vector<U>>;
};
template <class T, std::size_t N, bool is_const>
struct container_helper<std::array<T, N>, is_const> : container_helper_base::random_access<std::array<T, N>, is_const> {
using container_helper_base::random_access<std::array<T, N>, is_const>::random_access;
using iterated_type = T;
std::size_t insertion_index = 0;
template <typename PositionIterator, typename Value>
inline void insert(PositionIterator, Value&& val) {
this->container[insertion_index++] = std::forward<Value>(val);
}
template <typename U>
using change_value_type = typename std::array<U, N>;
};
template <class T, class Allocator, bool is_const>
struct container_helper<std::deque<T, Allocator>, is_const> : container_helper_base::random_access<std::deque<T, Allocator>, is_const> {
using container_helper_base::random_access<std::deque<T, Allocator>, is_const>::random_access;
using iterated_type = T;
template <typename U>
using change_value_type = typename std::deque<U>;
};
template <class T, class Allocator, bool is_const>
struct container_helper<std::list<T, Allocator>, is_const> : container_helper_base::base<std::list<T, Allocator>, is_const> {
using container_helper_base::base<std::list<T, Allocator>, is_const>::base;
using iterated_type = T;
template <typename U>
using change_value_type = typename std::list<U>;
};
template <class T, class Allocator>
struct container_helper<std::forward_list<T, Allocator>, false> : container_helper_base::base<std::forward_list<T, Allocator>, false> {
protected:
using List = typename std::forward_list<T, Allocator>;
typename List::iterator inserting_iterator;
public:
inline container_helper(List& list)
: container_helper_base::base<List, false>{list}, inserting_iterator(list.before_begin()) {}
using iterated_type = T;
inline signed_size_t size() const {
return -1;
};
template <typename PositionIterator, typename Value>
inline void insert(PositionIterator, Value&& val) {
this->container.insert_after(inserting_iterator, std::forward<Value>(val));
++inserting_iterator;
}
template <typename U>
using change_value_type = typename std::forward_list<U>;
};
template <class T, class Allocator>
struct container_helper<std::forward_list<T, Allocator>, true> : container_helper_base::base<std::forward_list<T, Allocator>, true> {
using container_helper_base::base<std::forward_list<T, Allocator>, true>::base;
using iterated_type = T;
inline signed_size_t size() const {
return -1;
};
template <typename U>
using change_value_type = typename std::forward_list<U>;
};
template <class T, class Compare, class Allocator, bool is_const>
struct container_helper<std::set<T, Compare, Allocator>, is_const> : container_helper_base::set<std::set<T, Compare, Allocator>, is_const> {
using container_helper_base::set<std::set<T, Compare, Allocator>, is_const>::set;
using iterated_type = T;
template <typename U>
using change_value_type = typename container_selector<U>::set;
};
template <class T, class Compare, class Allocator, bool is_const>
struct container_helper<std::multiset<T, Compare, Allocator>, is_const> : container_helper_base::set<std::multiset<T, Compare, Allocator>, is_const> {
using container_helper_base::set<std::multiset<T, Compare, Allocator>, is_const>::set;
using iterated_type = T;
template <typename U>
using change_value_type = typename container_selector<U>::multiset;
};
template <class Key, class Hash, class Pred, class Allocator, bool is_const>
struct container_helper<std::unordered_set<Key, Hash, Pred, Allocator>, is_const> : container_helper_base::set<std::unordered_set<Key, Hash, Pred, Allocator>, is_const> {
using container_helper_base::set<std::unordered_set<Key, Hash, Pred, Allocator>, is_const>::set;
using iterated_type = Key;
template <typename U>
using change_value_type = typename container_selector<U>::set;
};
template <class Key, class Hash, class Pred, class Allocator, bool is_const>
struct container_helper<std::unordered_multiset<Key, Hash, Pred, Allocator>, is_const> : container_helper_base::set<std::unordered_multiset<Key, Hash, Pred, Allocator>, is_const> {
using container_helper_base::set<std::unordered_multiset<Key, Hash, Pred, Allocator>, is_const>::set;
using iterated_type = Key;
template <typename U>
using change_value_type = typename container_selector<U>::multiset;
};
template <class Key, class T, class Compare, class Allocator, bool is_const>
struct container_helper<std::map<Key, T, Compare, Allocator>, is_const> : container_helper_base::map<std::map<Key, T, Compare, Allocator>, is_const> {
using container_helper_base::map<std::map<Key, T, Compare, Allocator>, is_const>::map;
using iterated_type = std::pair<Key, T>;
template <typename U>
using change_value_type = typename std::map<Key, U, Compare>;
};
template <class Key, class T, class Compare, class Allocator, bool is_const>
struct container_helper<std::multimap<Key, T, Compare, Allocator>, is_const> : container_helper_base::map<std::multimap<Key, T, Compare, Allocator>, is_const> {
using container_helper_base::map<std::multimap<Key, T, Compare, Allocator>, is_const>::map;
using iterated_type = std::pair<Key, T>;
template <typename U>
using change_value_type = typename std::multimap<Key, U, Compare>;
};
template <class Key, class T, class Hash, class Pred, class Allocator, bool is_const>
struct container_helper<std::unordered_map<Key, T, Hash, Pred, Allocator>, is_const> : container_helper_base::map<std::unordered_map<Key, T, Hash, Pred, Allocator>, is_const> {
using container_helper_base::map<std::unordered_map<Key, T, Hash, Pred, Allocator>, is_const>::map;
using iterated_type = std::pair<Key, T>;
template <typename U>
using change_value_type = typename std::unordered_map<Key, U, Hash, Pred>;
};
template <class Key, class T, class Hash, class Pred, class Allocator, bool is_const>
struct container_helper<std::unordered_multimap<Key, T, Hash, Pred, Allocator>, is_const> : container_helper_base::map<std::unordered_multimap<Key, T, Hash, Pred, Allocator>, is_const> {
using container_helper_base::map<std::unordered_multimap<Key, T, Hash, Pred, Allocator>, is_const>::map;
using iterated_type = std::pair<Key, T>;
template <typename U>
using change_value_type = typename std::unordered_multimap<Key, U, Hash, Pred>;
};
} // namespace _internal
template <class Container, typename MappingFunction>
inline auto mapped(Container&& container, MappingFunction&& fn) {
_internal::container_helper helper(container);
using U = typename decltype(helper)::template invoke_result_t<MappingFunction>;
using ResultType = typename decltype(helper)::template change_value_type<U>;
if constexpr (std::is_base_of_v<ResultType, Container /* rvalue */> && !std::is_const_v<Container> && decltype(helper)::value_settable) {
for (auto it = std::begin(container); it != std::end(container); ++it) {
helper.set_value(it, helper.invoke(fn, it));
}
return container;
} else {
ResultType res;
_internal::container_helper res_helper(res);
if (helper.size() >= 0) res_helper.reserve(helper.size());
for (auto it = std::begin(container); it != std::end(container); ++it) {
res_helper.insert(it, helper.invoke(fn, it));
}
return res;
}
}
template <class Container>
inline auto sorted(Container&& container) {
_internal::container_helper helper(container);
using T = typename decltype(helper)::iterated_type;
if constexpr (std::is_base_of_v<std::vector<T>, Container /* rvalue */> && !std::is_const_v<Container>) {
std::sort(container.begin(), container.end());
return container;
} else {
std::vector<T> res(std::begin(container), std::end(container));
std::sort(res.begin(), res.end());
return res;
}
}
template <class Container, typename KeyFunction>
inline auto sorted(Container&& container, KeyFunction&& fn) {
_internal::container_helper helper(container);
using T = typename decltype(helper)::iterated_type;
using U = typename decltype(helper)::template invoke_result_t<KeyFunction>;
using P = std::pair<decltype(std::begin(container)), U>;
std::vector<P> temp;
if (helper.size() >= 0) temp.reserve(helper.size());
for (auto it = std::begin(container); it != std::end(container); ++it) {
temp.emplace_back(it, helper.invoke(fn, it));
}
std::sort(temp.begin(), temp.end(), [](const P& lhs, const P& rhs) { return lhs.second < rhs.second; });
if constexpr (std::is_base_of_v<std::vector<T>, Container /* rvalue */> && !std::is_const_v<Container>) {
for (std::size_t i = 0; i < container.size(); ++i) container[i] = *temp[i].first;
return container;
} else {
std::vector<T> res;
res.reserve(temp.size());
for (auto&& [it, u] : temp) res.push_back(*it);
return res;
}
}
template <class Container>
inline auto ranked(Container&& container) {
_internal::container_helper helper(container);
using T = typename decltype(helper)::value_type;
std::vector<T> vals;
if (helper.size() >= 0) vals.reserve(helper.size());
for (auto it = std::begin(container); it != std::end(container); ++it) {
vals.push_back(helper.get_value(it));
}
std::sort(vals.begin(), vals.end());
vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
return mapped(
std::forward<Container>(container),
[&vals](const T& val) -> _internal::signed_size_t {
return std::lower_bound(vals.begin(), vals.end(), val) - vals.begin();
});
}
template <class Container, typename KeyFunction>
inline auto ranked(Container&& container, KeyFunction&& fn) {
_internal::container_helper helper(container);
// using T = typename decltype(helper)::value_type;
using U = typename decltype(helper)::template invoke_result_t<KeyFunction>;
std::vector<U> temp;
if (helper.size() >= 0) temp.reserve(helper.size());
for (auto it = std::begin(container); it != std::end(container); ++it) {
temp.push_back(helper.invoke(fn, it));
}
std::vector<U> keys(temp);
std::sort(keys.begin(), keys.end());
keys.erase(std::unique(keys.begin(), keys.end()), keys.end());
std::size_t i = 0;
return mapped(
std::forward<Container>(container),
[&keys, &temp, &i]() -> _internal::signed_size_t {
return std::lower_bound(keys.begin(), keys.end(), temp[i++]) - keys.begin();
});
}
template <class Container>
inline auto inversed(Container&& container) {
_internal::container_helper helper(container);
static_assert(decltype(helper)::subscriptable, "given container is not subscriptable");
using K = typename decltype(helper)::key_type;
using V = typename decltype(helper)::value_type;
typename _internal::container_selector<V>::template map<K> res;
for (auto it = std::begin(container); it != std::end(container); ++it) {
res[helper.get_value(it)] = helper.get_key(it);
}
return res;
}
template <class Container>
inline auto tallied(Container&& container) {
_internal::container_helper helper(container);
using T = typename decltype(helper)::value_type;
typename _internal::container_selector<T>::template map<_internal::signed_size_t> res;
for (auto it = std::begin(container); it != std::end(container); ++it) {
res[helper.get_value(it)] += 1;
}
return res;
}
template <class Container, class ConditionFn>
inline auto filtered(Container&& container, ConditionFn&& fn) {
std::remove_const_t<std::remove_reference_t<Container>> res;
_internal::container_helper helper(container);
_internal::container_helper res_helper(res);
for (auto it = std::begin(container); it != std::end(container); ++it) {
if (helper.invoke(fn, it)) res_helper.insert(it, helper.get_value(it));
}
return res;
}
} // namespace mihatsu
#endif
#ifndef _CPPEXPANDER_BB2113C90C224C2F
#define _CPPEXPANDER_BB2113C90C224C2F
#ifdef DEBUG
#include <iostream>
#include <string>
#include <tuple>
#include <type_traits>
namespace mihatsu::_internal {
template <std::nullptr_t = nullptr>
struct DebugPrinter {
std::ostream& os = std::cerr;
const std::string sep = " ";
const char* str;
DebugPrinter(const char* file, int line, const char* str)
: str(str) {
os << file << ":" << line << sep;
}
void operator()() {
os << std::endl;
}
template <typename Head, typename... Tail>
void operator()(const Head& head, const Tail&... tail) {
int paren_level = 0;
for (; *str != 0; ++str) {
if (*str == '(') {
++paren_level;
} else if (*str == ')') {
--paren_level;
} else if (paren_level == 0 && *str == ',') {
break;
}
if (*str != ' ') std::cerr << *str;
}
if (*str != 0) ++str;
os << "=";
print_value(head);
os << sep;
this->operator()(tail...);
}
template <typename T>
inline void print_value(const T& x) {
if constexpr (std::is_base_of_v<std::string, T>) {
os << x;
} else if constexpr (is_maplike_v<T> || is_setlike_v<T> || is_container_v<T> || std::is_array_v<T>) {
if constexpr (is_maplike_v<T> || is_setlike_v<T>) {
os << "{";
} else {
os << "[";
}
bool is_first = true;
for (auto&& value : x) {
os << (is_first ? "" : " ");
is_first = false;
if constexpr (is_maplike_v<T>) {
print_value(value.first);
os << ":";
print_value(value.second);
} else {
print_value(value);
}
}
if constexpr (is_maplike_v<T> || is_setlike_v<T>) {
os << "}";
} else {
os << "]";
}
} else if constexpr (is_pairlike_v<T>) {
os << "(";
print_value(x.first);
os << ",";
print_value(x.second);
os << ")";
} else {
os << x;
}
}
inline void print_value(const char* str) {
os << str;
}
inline void print_value(bool val) {
os << (val ? "true" : "false");
}
template <typename... T>
inline void print_value(const std::tuple<T...>& tuple) {
print_tuple_impl<0>(tuple);
}
template <int index, typename... T>
inline void print_tuple_impl(const std::tuple<T...>& tuple) {
if constexpr (index == 0) os << "(";
if constexpr (index < sizeof...(T)) {
if constexpr (index > 0) os << ",";
print_value(std::get<index>(tuple));
print_tuple_impl<index + 1>(tuple);
} else {
os << ")";
}
}
};
} // namespace mihatsu::_internal
#define debug_print(...) (mihatsu::_internal::DebugPrinter(__FILE__, __LINE__, #__VA_ARGS__)(__VA_ARGS__))
#else
#define debug_print(...) ([]() {})()
#endif
#endif
#ifndef _CPPEXPANDER_6D45E8C487FAC57C
#define _CPPEXPANDER_6D45E8C487FAC57C
#include <functional>
#include <type_traits>
namespace mihatsu {
template <typename T, typename U>
inline T& chmax(T& x, U&& y) {
return (x < y) ? (x = std::forward<U>(y)) : x;
}
template <typename T, typename U>
inline T& chmin(T& x, U&& y) {
return (y < x) ? (x = std::forward<U>(y)) : x;
}
template <class T, class U, std::enable_if_t<!std::is_same_v<T, U>>* = nullptr>
inline constexpr std::common_type_t<T, U> max(const T& t, const U& u) {
return t < u ? static_cast<std::common_type_t<T, U>>(u) : static_cast<std::common_type_t<T, U>>(t);
}
template <class T, class U, std::enable_if_t<!std::is_same_v<T, U>>* = nullptr>
inline constexpr std::common_type_t<T, U> min(const T& t, const U& u) {
return t < u ? static_cast<std::common_type_t<T, U>>(t) : static_cast<std::common_type_t<T, U>>(u);
}
} // namespace mihatsu
#endif
#ifndef _CPPEXPANDER_94BDE4569D6CF65A
#define _CPPEXPANDER_94BDE4569D6CF65A
#ifndef _CPPEXPANDER_B613421126DD2845
#define _CPPEXPANDER_B613421126DD2845
#ifndef MIHATSU_B2E_STORE_SIZE
#define MIHATSU_B2E_STORE_SIZE 10
#endif
static_assert(MIHATSU_B2E_STORE_SIZE > 0, "MIHATSU_B2E_STORE_SIZE must be greater than 0");
#include <iterator>
#include <memory>
#include <type_traits>
#include <utility>
namespace mihatsu::_internal {
template <typename T, int id>
struct b2e_impl {
private:
static std::unique_ptr<T> ptr;
static int counter;
public:
static inline bool is_first() noexcept {
return ++counter % 2 == 1;
}
// first call
static inline auto begin(T&& val) {
ptr = std::make_unique<T>(std::forward<T>(val));
return begin();
}
static inline auto end(T&& val) {
ptr = std::make_unique<T>(std::forward<T>(val));
return end();
}
static inline auto rbegin(T&& val) {
ptr = std::make_unique<T>(std::forward<T>(val));
return rbegin();
}
static inline auto rend(T&& val) {
ptr = std::make_unique<T>(std::forward<T>(val));
return rend();
}
// second call
static inline auto begin() {
return std::begin(*ptr);
}
static inline auto end() {
return std::end(*ptr);
}
static inline auto rbegin() {
return std::rbegin(*ptr);
}
static inline auto rend() {
return std::rend(*ptr);
}
// not called (written only for type consistency)
static inline auto begin(T& val) {
return std::begin(val);
}
static inline auto end(T& val) {
return std::end(val);
}
static inline auto rbegin(T& val) {
return std::rbegin(val);
}
static inline auto rend(T& val) {
return std::rend(val);
}
};
template <typename T, int id>
inline int b2e_impl<T, id>::counter = 0;
template <typename T, int id>
inline std::unique_ptr<T> b2e_impl<T, id>::ptr;
#define b2e(...) _MIHATSU_B2E((__VA_ARGS__), begin, end)
#define e2b(...) _MIHATSU_B2E((__VA_ARGS__), rbegin, rend)
#define _MIHATSU_B2E(val, begin_name, end_name) _MIHATSU_B2E_IMPL(val, begin_name, end_name, mihatsu::_internal::b2e_impl, std::remove_reference_t<decltype(val)>, __COUNTER__ % MIHATSU_B2E_STORE_SIZE)
#define _MIHATSU_B2E_IMPL(val, begin_name, end_name, impl, T, id) _MIHATSU_B2E_EXPR(begin_name, val, impl, T, id), _MIHATSU_B2E_EXPR(end_name, val, impl, T, id)
#define _MIHATSU_B2E_EXPR(name, val, impl, T, id) \
(std::is_reference_v<decltype((val))> ? std::name(val) \
: impl<T, id>::is_first() ? static_cast<decltype(std::name(val))>(impl<T, id>::name(val)) \
: static_cast<decltype(std::name(val))>(impl<T, id>::name()))
} // namespace mihatsu::_internal
#endif
#ifndef _CPPEXPANDER_5904F07D86022530
#define _CPPEXPANDER_5904F07D86022530
#include <tuple>
namespace mihatsu::_internal::lambda_shorthand {
template <std::size_t N>
struct _MissingArg {};
} // namespace mihatsu::_internal::lambda_shorthand
#define L(...) ([&](auto&&... _args) -> decltype(auto) { \
auto _expr = [&](auto&& $1, auto&& $2, auto&& $3, auto&& $4, auto&& $5, auto&& $6, auto&& $7, auto&& $8, auto&& $9) -> decltype(auto) { return (__VA_ARGS__); }; \
auto _argt = std::forward_as_tuple(_args...); \
using mihatsu::_internal::lambda_shorthand::_MissingArg; \
\
if constexpr (sizeof...(_args) == 0) { \
return _expr(_MissingArg<1>(), _MissingArg<2>(), _MissingArg<3>(), _MissingArg<4>(), _MissingArg<5>(), _MissingArg<6>(), _MissingArg<7>(), _MissingArg<8>(), _MissingArg<9>()); \
} else if constexpr (sizeof...(_args) == 1) { \
return _expr(std::get<0>(_argt), _MissingArg<2>(), _MissingArg<3>(), _MissingArg<4>(), _MissingArg<5>(), _MissingArg<6>(), _MissingArg<7>(), _MissingArg<8>(), _MissingArg<9>()); \
} else if constexpr (sizeof...(_args) == 2) { \
return _expr(std::get<0>(_argt), std::get<1>(_argt), _MissingArg<3>(), _MissingArg<4>(), _MissingArg<5>(), _MissingArg<6>(), _MissingArg<7>(), _MissingArg<8>(), _MissingArg<9>()); \
} else if constexpr (sizeof...(_args) == 3) { \
return _expr(std::get<0>(_argt), std::get<1>(_argt), std::get<2>(_argt), _MissingArg<4>(), _MissingArg<5>(), _MissingArg<6>(), _MissingArg<7>(), _MissingArg<8>(), _MissingArg<9>()); \
} else if constexpr (sizeof...(_args) == 4) { \
return _expr(std::get<0>(_argt), std::get<1>(_argt), std::get<2>(_argt), std::get<3>(_argt), _MissingArg<5>(), _MissingArg<6>(), _MissingArg<7>(), _MissingArg<8>(), _MissingArg<9>()); \
} else if constexpr (sizeof...(_args) == 5) { \
return _expr(std::get<0>(_argt), std::get<1>(_argt), std::get<2>(_argt), std::get<3>(_argt), std::get<4>(_argt), _MissingArg<6>(), _MissingArg<7>(), _MissingArg<8>(), _MissingArg<9>()); \
} else if constexpr (sizeof...(_args) == 6) { \
return _expr(std::get<0>(_argt), std::get<1>(_argt), std::get<2>(_argt), std::get<3>(_argt), std::get<4>(_argt), std::get<5>(_argt), _MissingArg<7>(), _MissingArg<8>(), _MissingArg<9>()); \
} else if constexpr (sizeof...(_args) == 7) { \
return _expr(std::get<0>(_argt), std::get<1>(_argt), std::get<2>(_argt), std::get<3>(_argt), std::get<4>(_argt), std::get<5>(_argt), std::get<6>(_argt), _MissingArg<8>(), _MissingArg<9>()); \
} else if constexpr (sizeof...(_args) == 8) { \
return _expr(std::get<0>(_argt), std::get<1>(_argt), std::get<2>(_argt), std::get<3>(_argt), std::get<4>(_argt), std::get<5>(_argt), std::get<6>(_argt), std::get<7>(_argt), _MissingArg<9>()); \
} else { \
return _expr(std::get<0>(_argt), std::get<1>(_argt), std::get<2>(_argt), std::get<3>(_argt), std::get<4>(_argt), std::get<5>(_argt), std::get<6>(_argt), std::get<7>(_argt), std::get<8>(_argt)); \
} \
})
#endif
#ifndef _CPPEXPANDER_3C14173F744F56F2
#define _CPPEXPANDER_3C14173F744F56F2
#include <iterator>
#include <type_traits>
#ifndef _CPPEXPANDER_EBDFFE5A6B17FE69
#define _CPPEXPANDER_EBDFFE5A6B17FE69
#define MIHATSU_CONCAT(a, b) _MIHATSU_PRIMITIVE_CONCAT(a, b)
#define _MIHATSU_PRIMITIVE_CONCAT(a, b) a##b
#define MIHATSU_NARGS(...) _MIHATSU_SELECT_11TH(__VA_ARGS__, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
#define _MIHATSU_SELECT_11TH(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, ...) _11
#define MIHATSU_NARGS_SELECTOR(prefix, ...) MIHATSU_CONCAT(prefix, MIHATSU_NARGS(__VA_ARGS__))(__VA_ARGS__)
#define MIHATSU_IS_BRACKETED(token) MIHATSU_NARGS_SELECTOR(_MIHATSU_IS_BRACKETED_IMPL, _MIHATSU_0_COMMA_0 token)
#define _MIHATSU_0_COMMA_0(...) 0, 0
#define _MIHATSU_IS_BRACKETED_IMPL1(...) 0
#define _MIHATSU_IS_BRACKETED_IMPL2(...) 1
#define MIHATSU_CONDITIONAL(cond, case_1, case_0) MIHATSU_CONCAT(_MIHATSU_CONDITIONAL_IMPL, cond)(case_1, case_0)
#define _MIHATSU_CONDITIONAL_IMPL1(case_1, case_0) case_1
#define _MIHATSU_CONDITIONAL_IMPL0(case_1, case_0) case_0
#endif
namespace mihatsu::_internal::rep_impl {
template <class T>
struct numeric_range {
T size;
constexpr inline numeric_range(const T& size) noexcept
: size(size) {}
class iterator {
friend numeric_range<T>;
T val;
constexpr inline iterator(const T& val) noexcept
: val(val) {}
public:
inline iterator& operator++() noexcept {
++val;
return *this;
}
constexpr inline T& operator*() noexcept {
return val;
}
constexpr inline bool operator!=(const iterator& other) const noexcept {
return val < other.val;
}
};
constexpr inline iterator begin() const noexcept { return iterator(0); }
constexpr inline iterator end() const noexcept { return iterator(size); }
class reverse_iterator {
friend numeric_range<T>;
T val;
constexpr inline reverse_iterator(const T& val) noexcept
: val(val) {}
public:
inline reverse_iterator& operator++() noexcept {
--val;
return *this;
}
constexpr inline T& operator*() noexcept {
return val;
}
constexpr inline bool operator!=(const reverse_iterator& other) const noexcept {
return val >= other.val;
}
};
constexpr inline reverse_iterator rbegin() const noexcept { return reverse_iterator(size - 1); }
constexpr inline reverse_iterator rend() const noexcept { return reverse_iterator(0); }
};
template <class T, std::enable_if_t<is_container_v<std::remove_reference_t<T>>>* = nullptr>
constexpr inline decltype(auto) range(T&& x) {
return x;
}
template <class T, std::enable_if_t<!is_container_v<std::remove_reference_t<T>>>* = nullptr>
constexpr inline decltype(auto) range(T&& x) {
return numeric_range<std::remove_reference_t<T>>(x);
}
template <std::nullptr_t = nullptr>
struct breaking_state {
static bool flag;
static inline void do_break() noexcept {
flag = true;
}
static inline bool check() noexcept {
bool res = !flag;
flag = false;
return res;
}
};
template <std::nullptr_t _>
inline bool breaking_state<_>::flag = false;
} // namespace mihatsu::_internal::rep_impl
#define rep(var, ...) \
if (mihatsu::_internal::rep_impl::breaking_state<>::check()) \
MIHATSU_CONDITIONAL(MIHATSU_IS_BRACKETED(var), _MIHATSU_REP_BRACKETED, _MIHATSU_REP) \
(var, __VA_ARGS__)
#define _MIHATSU_REP(...) MIHATSU_NARGS_SELECTOR(_MIHATSU_REP, __VA_ARGS__)
#define _MIHATSU_REP2(i, n) \
if (auto&& _##i##_range = (n); true) _MIHATSU_REP_RANGE(i, mihatsu::_internal::rep_impl::range(_##i##_range))
#define _MIHATSU_REP3(i, a, b) for (std::common_type_t<decltype(a), decltype(b)> i = (a), _##i##_end = (b); i != _##i##_end; ++i)
#define _MIHATSU_REP4(i, a, b, c) for (std::common_type_t<decltype(a), decltype(b), decltype(c)> i = (a), _##i##_end = (b), _##i##_step = (c); _##i##_step > 0 ? i < _##i##_end : i > _##i##_end; i += _##i##_step)
#define _MIHATSU_REP_BRACKETED(vars, ...) _MIHATSU_REP_RANGE(_MIHATSU_REP_BRACKETED_VARS vars, (__VA_ARGS__))
#define _MIHATSU_REP_BRACKETED_VARS(...) [__VA_ARGS__]
#define _MIHATSU_REP_RANGE(var, range) for (auto&& var : range)
#define rep_rev(var, ...) \
if (mihatsu::_internal::rep_impl::breaking_state<>::check()) \
MIHATSU_CONDITIONAL(MIHATSU_IS_BRACKETED(var), _MIHATSU_REPREV_BRACKETED, _MIHATSU_REPREV) \
(var, __VA_ARGS__)
#define _MIHATSU_REPREV(...) MIHATSU_NARGS_SELECTOR(_MIHATSU_REPREV, __VA_ARGS__)
#define _MIHATSU_REPREV2(i, n) \
if (auto&& _##i##_range = (n); true) _MIHATSU_REPREV_RANGE(__COUNTER__, mihatsu::_internal::rep_impl::range(_##i##_range), i)
#define _MIHATSU_REPREV3(i, a, b) for (std::common_type_t<decltype(a), decltype(b)> i = b - 1, _##i##_end = a - 1; i != _##i##_end; --i)
#define _MIHATSU_REPREV_BRACKETED(vars, ...) _MIHATSU_REPREV_RANGE(__COUNTER__, (__VA_ARGS__), _MIHATSU_REP_BRACKETED_VARS vars)
#define _MIHATSU_REPREV_RANGE(...) _MIHATSU_REPREV_RANGE_IMPL(__VA_ARGS__)
#define _MIHATSU_REPREV_RANGE_IMPL(id, range, ...) \
if (auto&& _reprev##id##_range = range; true) \
if (auto _reprev##id##_begin = std::rbegin(_reprev##id##_range); true) \
if (auto _reprev##id##_end = std::rend(_reprev##id##_range); true) \
for (; _reprev##id##_begin != _reprev##id##_end; ++_reprev##id##_begin) \
if (auto&& __VA_ARGS__ = *_reprev##id##_begin; true)
#define break(label) \
{ \
mihatsu::_internal::rep_impl::breaking_state<>::do_break(); \
goto label; \
} \
([]() {}())
#endif
#endif
#ifndef _CPPEXPANDER_AFF6F3819DCDD0CF
#define _CPPEXPANDER_AFF6F3819DCDD0CF
#include <functional>
#include <iostream>
#include <tuple>
#include <type_traits>
#include <utility>
// ---- overload operators for pair ----
namespace std {
template <typename T, typename U, enable_if_t<mihatsu::_internal::is_pairlike_v<T> && mihatsu::_internal::is_pairlike_v<U>>* = nullptr>
constexpr inline auto operator+(const T& lhs, const U& rhs) {
return std::make_pair(lhs.first + rhs.first, lhs.second + rhs.second);
}
template <typename T, typename U, enable_if_t<mihatsu::_internal::is_pairlike_v<T> && mihatsu::_internal::is_pairlike_v<U>>* = nullptr>
constexpr inline auto operator-(const T& lhs, const U& rhs) {
return std::make_pair(lhs.first - rhs.first, lhs.second - rhs.second);
}
template <typename T, enable_if_t<mihatsu::_internal::is_pairlike_v<T>>* = nullptr>
constexpr inline auto operator-(const T& pair) {
return std::make_pair(-pair.first, -pair.second);
}
template <typename T, typename U, enable_if_t<mihatsu::_internal::is_pairlike_v<T>>* = nullptr>
constexpr inline auto operator*(const T& lhs, const U& rhs) {
return std::make_pair(lhs.first * rhs, lhs.second * rhs);
}
template <typename T, typename U, enable_if_t<mihatsu::_internal::is_pairlike_v<U>>* = nullptr>
constexpr inline auto operator*(const T& lhs, const U& rhs) {
return std::make_pair(lhs * rhs.first, lhs * rhs.second);
}
template <typename T, typename U, enable_if_t<mihatsu::_internal::is_pairlike_v<T>>* = nullptr>
constexpr inline auto operator/(const T& lhs, const U& rhs) {
return std::make_pair(lhs.first / rhs, lhs.second / rhs);
}
template <typename T, typename U, enable_if_t<mihatsu::_internal::is_pairlike_v<T> && mihatsu::_internal::is_pairlike_v<U>>* = nullptr>
constexpr inline T& operator+=(T& lhs, const U& rhs) {
lhs.first += rhs.first;
lhs.second += rhs.second;
return lhs;
}
template <typename T, typename U, enable_if_t<mihatsu::_internal::is_pairlike_v<T> && mihatsu::_internal::is_pairlike_v<U>>* = nullptr>
constexpr inline T& operator-=(T& lhs, const U& rhs) {
lhs.first -= rhs.first;
lhs.second -= rhs.second;
return lhs;
}
template <typename T, typename U, enable_if_t<mihatsu::_internal::is_pairlike_v<T>>* = nullptr>
constexpr inline T& operator*=(T& lhs, const U& rhs) {
lhs.first *= rhs;
lhs.second *= rhs;
return lhs;
}
template <typename T, typename U, enable_if_t<mihatsu::_internal::is_pairlike_v<T>>* = nullptr>
constexpr inline T& operator/=(T& lhs, const U& rhs) {
lhs.first /= rhs;
lhs.second /= rhs;
return lhs;
}
template <typename T, enable_if_t<mihatsu::_internal::is_pairlike_v<T>>* = nullptr>
inline istream& operator>>(istream& is, T& pair) {
return is >> pair.first >> pair.second;
}
} // namespace std
// ---- overload operators for tuple ----
namespace mihatsu::_internal {
template <int index, typename... T>
inline std::istream& input_tuple_impl(std::istream& is, std::tuple<T...>& tuple) {
if constexpr (index < sizeof...(T)) {
is >> std::get<index>(tuple);
return input_tuple_impl<index + 1>(is, tuple);
} else {
return is;
}
}
} // namespace mihatsu::_internal
namespace std {
template <typename... T>
inline istream& operator>>(istream& is, tuple<T...>& tuple) {
return mihatsu::_internal::input_tuple_impl<0>(is, tuple);
}
} // namespace std
// ---- hash function for pair and tuple ----
namespace mihatsu::_internal {
inline std::size_t hash_sequence() {
return 0;
}
template <typename Head, typename... Tail>
inline std::size_t hash_sequence(const Head& head, const Tail&... tail) {
const auto seed = hash_sequence(tail...);
return std::hash<Head>()(head) + 0x4cc1a90e + (seed << 23) + (seed >> 11) ^ seed;
}
} // namespace mihatsu::_internal
namespace std {
template <typename T1, typename T2>
class hash<pair<T1, T2>> {
public:
inline size_t operator()(const pair<T1, T2>& pair) const {
return mihatsu::_internal::hash_sequence(pair.first, pair.second);
}
};
template <typename... T>
class hash<tuple<T...>> {
public:
inline size_t operator()(const tuple<T...>& tuple) const {
return apply(mihatsu::_internal::hash_sequence<T...>, tuple);
}
};
} // namespace std
#endif
#ifndef _CPPEXPANDER_D421F0B1646BEA36
#define _CPPEXPANDER_D421F0B1646BEA36
#include <functional>
#include <iostream>
#include <memory>
#include <vector>
// -------- input --------
namespace std {
template <class T, class Allocator>
inline istream& operator>>(istream& is, vector<T, Allocator>& vector) {
for (auto&& p : vector) cin >> p;
return is;
}
} // namespace std
// -------- output --------
namespace mihatsu::_internal {
template <class T, class Allocator>
struct VectorPrinter {
std::ostream& os;
using Vector = std::vector<T, Allocator>;
const Vector* ptr_l = nullptr;
std::unique_ptr<const Vector> ptr_r;
VectorPrinter(std::ostream& os, const Vector& vector)
: os(os), ptr_l(&vector) {}
VectorPrinter(std::ostream& os, Vector&& vector)
: os(os), ptr_r(std::make_unique<Vector>(std::forward<Vector>(vector))) {}
inline const Vector& get_vector() {
return (this->ptr_l != nullptr) ? *(this->ptr_l) : *(this->ptr_r);
}
template <typename Delimiter>
std::ostream& operator<<(const Delimiter& delimiter) {
bool is_first = true;
for (auto&& v : get_vector()) {
if (!is_first) os << delimiter;
is_first = false;
os << v;
}
return os;
}
};
} // namespace mihatsu::_internal
namespace std {
template <class T, class Allocator>
inline auto operator<<(ostream& os, const vector<T, Allocator>& vector) {
return mihatsu::_internal::VectorPrinter(os, vector);
}
template <class T, class Allocator>
inline auto operator<<(ostream& os, vector<T, Allocator>&& vector) {
return mihatsu::_internal::VectorPrinter(os, std::forward<std::vector<T, Allocator>>(vector));
}
} // namespace std
#endif
#ifndef _CPPEXPANDER_FA63E65F1AA0BB91
#define _CPPEXPANDER_FA63E65F1AA0BB91
#include <iostream>
#include <type_traits>
#include <utility>
namespace mihatsu {
template <typename T, typename = void>
struct with_input {
static_assert(_internal::false_v<T>, "with_input does not support this type");
};
template <typename T>
struct with_input<T, std::enable_if_t<std::is_arithmetic_v<T>>> {
private:
T val;
class input_error : public std::exception {
const char* what() const noexcept {
return "failed reading std::cin";
}
};
public:
inline with_input() {
std::cin >> val;
if (!std::cin) throw input_error();
}
constexpr inline with_input(const T& val) noexcept
: val(val) {}
constexpr inline with_input(T&& val) noexcept
: val(std::forward<T>(val)) {}
constexpr inline operator const T&() const noexcept {
return val;
}
constexpr inline operator T&() noexcept {
return val;
}
};
template <typename T>
struct with_input<T, std::enable_if_t<std::is_class_v<T>>> : public T {
private:
class input_error : public std::exception {
const char* what() const noexcept {
return "failed reading std::cin";
}
};
public:
using T::T;
inline with_input() {
std::cin >> *this;
if (!std::cin) throw input_error();
}
constexpr inline with_input(const T& val) noexcept
: T{val} {}
constexpr inline with_input(T&& val) noexcept
: T{std::forward<T>(val)} {}
};
} // namespace mihatsu
namespace std {
template <typename T, typename U>
struct common_type<mihatsu::with_input<T>, U> {
using type = typename common_type<T, U>::type;
};
template <typename T, typename U>
struct common_type<T, mihatsu::with_input<U>> {
using type = typename common_type<T, U>::type;
};
template <typename T, typename U>
struct common_type<mihatsu::with_input<T>, mihatsu::with_input<U>> {
using type = typename common_type<T, U>::type;
};
template <typename T>
class hash<mihatsu::with_input<T>> {
public:
inline size_t operator()(const mihatsu::with_input<T>& val) const {
return hash<T>()(val);
}
};
} // namespace std
#endif
template <typename T>
using V = std::vector<T>;
template <typename T>
using VV = V<V<T>>;
template <typename T>
using VVV = V<VV<T>>;
using ll = long long;
using ull = unsigned long long;
using pll = std::pair<ll, ll>;
using tll = std::tuple<ll, ll, ll>;
using vll = std::vector<ll>;
using dd = long double;
using lli = mihatsu::with_input<ll>;
using ulli = mihatsu::with_input<ull>;
using plli = std::pair<lli, lli>;
using tlli = std::tuple<lli, lli, lli>;
using vlli = std::vector<lli>;
using chari = mihatsu::with_input<char>;
using inti = mihatsu::with_input<int>;
using ddi = mihatsu::with_input<dd>;
using stringi = mihatsu::with_input<std::string>;
template <typename T>
using unpriority_queue = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr inline ll inf = std::numeric_limits<ll>::max() / 4;
constexpr inline char lf = '\n';
constexpr inline long double pi = 3.1415926535897932384626L;
inline auto operator"" _c(const char* str, std::size_t) {
return mihatsu::constructible_string<char>(str);
}
namespace mihatsu::_internal {
template <std::nullptr_t = nullptr>
struct Init {
Init() {
#ifndef DEBUG
std::cin.tie(0);
std::cout.tie(0);
std::ios::sync_with_stdio(0);
#endif
std::cout.precision(16);
}
};
inline Init init;
} // namespace mihatsu::_internal
using namespace std;
using namespace mihatsu;
// -------- 以下, 仮コード --------
namespace std {
template <typename T, enable_if_t<mihatsu::_internal::is_pairlike_v<T>>* = nullptr>
ostream& operator<<(ostream& os, const T& pair) {
return os << pair.first << " " << pair.second;
}
} // namespace std
namespace mihatsu::_internal {
template <class charT, class traits, class Allocator, bool is_const>
struct container_helper<mihatsu::with_input<std::basic_string<charT, traits, Allocator>>, is_const> : container_helper<std::basic_string<charT, traits, Allocator>, is_const> {
using container_helper<std::basic_string<charT, traits, Allocator>, is_const>::container_helper;
};
template <class charT, class traits, class Allocator, bool is_const>
struct container_helper<mihatsu::constructible_string<charT, traits, Allocator>, is_const> : container_helper<std::basic_string<charT, traits, Allocator>, is_const> {
using container_helper<std::basic_string<charT, traits, Allocator>, is_const>::container_helper;
};
} // namespace mihatsu::_internal
#endif
using namespace atcoder;
// -------- modint --------
namespace atcoder {
template <int m, void* _>
inline std::istream& operator>>(std::istream& s, static_modint<m, _>& x) {
long long v;
s >> v;
x = v;
return s;
}
template <int id>
inline std::istream& operator>>(std::istream& s, dynamic_modint<id>& x) {
long long v;
s >> v;
x = v;
return s;
}
template <int m, void* _>
inline std::ostream& operator<<(std::ostream& s, const static_modint<m, _>& x) {
return s << x.val();
}
template <int id>
inline std::ostream& operator<<(std::ostream& s, const dynamic_modint<id>& x) {
return s << x.val();
}
template <int m, void* _>
inline bool operator<(const static_modint<m, _>& lhs, const static_modint<m, _>& rhs) {
return lhs.val() < rhs.val();
}
template <int id>
inline bool operator<(const dynamic_modint<id>& lhs, const dynamic_modint<id>& rhs) {
return lhs.val() < rhs.val();
}
} // namespace atcoder
namespace std {
template <int m, void* _>
class hash<atcoder::static_modint<m, _>> {
public:
inline size_t operator()(const atcoder::static_modint<m, _>& x) const {
return x.val();
}
};
template <int id>
class hash<atcoder::dynamic_modint<id>> {
public:
inline size_t operator()(const atcoder::dynamic_modint<id>& x) const {
return x.val();
}
};
} // namespace std
// -------- segtree --------
#define DEFINE_SEGTREE(name, T, op, e) \
namespace _##name { \
inline T _op(T a, T b) { return (op); } \
inline T _e() { return (e); } \
using type = typename atcoder::segtree<T, _op, _e>; \
} \
using name = _##name::type;
#define DEFINE_LAZYSEGTREE(name, T, op, e, F, mapping, composition) \
namespace name { \
struct _T { \
T value; \
int left, right, size; \
inline _T(const T& value, int left, int right, int size) \
: value(value), left(left), right(right), size(size) {} \
inline _T(const T& value, int left = 0, int right = 1) \
: _T(value, left, right, right - left) {} \
inline _T() : _T((e), -1, -1, 0) {} \
}; \
inline _T _op(_T _a, _T _b) { \
const auto &a = _a.value, &b = _b.value; \
const int newLeft = (_a.size > 0 ? _a : _b).left; \
const int newRight = (_b.size > 0 ? _b : _a).right; \
const int newSize = _a.size + _b.size; \
return _T((op), newLeft, newRight, newSize); \
} \
inline _T _e() { return _T(); } \
struct _F { \
F value; \
bool enabled; \
inline _F(const F& value, bool enabled = true) \
: value(value), enabled(enabled) {} \
inline _F() : _F(F(), false) {} \
}; \
inline _T _mapping(_F _f, _T _a) { \
if (!_f.enabled) return _a; \
const auto& f = _f.value; \
const auto& a = _a.value; \
const int l = _a.left, r = _a.right, s = _a.size; \
return _T((mapping), _a.left, _a.right, _a.size); \
} \
inline _F _composition(_F _f, _F _g) { \
if (!_f.enabled) return _g; \
if (!_g.enabled) return _f; \
const auto &f = _f.value, &g = _g.value; \
return _F((composition), true); \
} \
inline _F _id() { return _F(); } \
using type = typename atcoder::lazy_segtree<_T, _op, _e, _F, _mapping, _composition, _id>; \
inline type generate(int n) { \
std::vector<_T> _v(n); \
for (int i = 0; i < n; ++i) _v[i] = _T(e, i, i + 1, 1); \
return type(std::move(_v)); \
} \
inline type generate(const std::vector<T>& v) { \
const int n = v.size(); \
std::vector<_T> _v(n); \
for (int i = 0; i < n; ++i) _v[i] = _T(v[i], i, i + 1, 1); \
return type(std::move(_v)); \
} \
}
#endif
int main() {
lli r, c;
V<stringi> b(r);
auto res = b;
rep(y, r) rep(x, c) {
auto v = b[y][x] - '0';
if (1 <= v && v <= 9) {
rep(y2, r) rep(x2, c) {
if (abs(y2 - y) + abs(x2 - x) <= v) {
res[y2][x2] = '.';
}
}
}
}
cout << res << "\n"
<< endl;
}
Submission Info
| Submission Time |
|
| Task |
B - Bombs |
| User |
mihatsu |
| Language |
C++ (GCC 9.2.1) |
| Score |
200 |
| Code Size |
67782 Byte |
| Status |
AC |
| Exec Time |
8 ms |
| Memory |
3688 KiB |
Judge Result
| Set Name |
Sample |
All |
| Score / Max Score |
0 / 0 |
200 / 200 |
| Status |
|
|
| Set Name |
Test Cases |
| Sample |
00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt |
| All |
00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt |
| Case Name |
Status |
Exec Time |
Memory |
| 00_sample_00.txt |
AC |
8 ms |
3524 KiB |
| 00_sample_01.txt |
AC |
3 ms |
3484 KiB |
| 00_sample_02.txt |
AC |
2 ms |
3596 KiB |
| 00_sample_03.txt |
AC |
2 ms |
3688 KiB |
| 01_random_00.txt |
AC |
2 ms |
3548 KiB |
| 01_random_01.txt |
AC |
2 ms |
3608 KiB |
| 01_random_02.txt |
AC |
2 ms |
3636 KiB |
| 01_random_03.txt |
AC |
3 ms |
3488 KiB |
| 01_random_04.txt |
AC |
2 ms |
3640 KiB |
| 01_random_05.txt |
AC |
2 ms |
3652 KiB |
| 01_random_06.txt |
AC |
3 ms |
3548 KiB |
| 01_random_07.txt |
AC |
2 ms |
3616 KiB |
| 01_random_08.txt |
AC |
2 ms |
3496 KiB |
| 01_random_09.txt |
AC |
2 ms |
3608 KiB |
| 01_random_10.txt |
AC |
2 ms |
3612 KiB |
| 01_random_11.txt |
AC |
2 ms |
3612 KiB |
| 01_random_12.txt |
AC |
3 ms |
3556 KiB |
| 01_random_13.txt |
AC |
2 ms |
3616 KiB |
| 01_random_14.txt |
AC |
4 ms |
3652 KiB |
| 01_random_15.txt |
AC |
2 ms |
3652 KiB |
| 01_random_16.txt |
AC |
3 ms |
3596 KiB |
| 01_random_17.txt |
AC |
2 ms |
3524 KiB |