#1104946 (C++23) No.1717 Levi-Civita Triangle

提出ソース
結果

問題	No.1717 Levi-Civita Triangle
ユーザー	みどりむし🦠
提出日時	2025-07-15 19:17:29
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	34 ms / 2,000 ms
コード長	48,890 bytes
コンパイル時間	3,323 ms
コンパイル使用メモリ	304,500 KB
実行使用メモリ	7,716 KB
最終ジャッジ日時	2025-07-15 19:17:38
合計ジャッジ時間	5,126 ms
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 42
権限があれば一括ダウンロードができます
ソースコード

raw source code
/*
 * @uni_kakurenbo
 * https://github.com/uni-kakurenbo/competitive-programming-workspace
 *
 * CC0 1.0  http://creativecommons.org/publicdomain/zero/1.0/deed.ja
 */
/* #language C++ 23 GCC */
// #define DEBUGGER_ENABLED
#include <bits/stdc++.h>
/* [begin]: snippet/aliases.hpp */
#include <cstdint>
#include <utility>
#include <vector>
#include <queue>
#include <ranges>
/* [begin]: macro/internal/compatibility.hpp */
#include <string>
/* [begin]: adaptor/string.hpp */
#include <algorithm>
/* [begin]: adaptor/internal/advanced_container.hpp */
#include <cassert>
/* [begin]: snippet/internal/base.hpp */
#define until(...) while(!(__VA_ARGS__))
#define CONTINUE(...) { __VA_ARGS__; continue; }
#define BREAK(...) { __VA_ARGS__; break; }
#define ALL(x) std::ranges::begin((x)),std::ranges::end((x))
#define RALL(x) std::ranges::rbegin((x)),std::ranges::rend((x))
#define $F first
#define $S second
/* [end]: snippet/internal/base.hpp*/
/* [begin]: snippet/iterations.hpp */
#include <type_traits>
/* [begin]: macro/overload.hpp */
#define $OVERLOAD2(arg0, arg1, cmd, ...) cmd
#define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd
#define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd
#define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd
#define $OVERLOAD6(arg0, arg1, arg2, arg3, arg4, arg5, cmd, ...) cmd
/* [end]: macro/overload.hpp*/
/* [begin]: macro/basic.hpp */
#define TO_STRING_AUX(x) #x
#define TO_STRING(x) TO_STRING_AUX(x)
#define CONCAT_AUX(x, y) x##y
#define CONCAT(x, y) CONCAT_AUX(x, y)
#define UNPAREN_AUX(...) __VA_ARGS__
#define UNPAREN(...) __VA_ARGS__
/* [end]: macro/basic.hpp*/
#define LOOP(n) REPI(CONCAT(_$, __COUNTER__), n)
#define REPI(i,n) for(std::remove_cvref_t<decltype(n)> i=0, CONCAT(i, $)=(n); i<CONCAT(i, $); ++i)
#define REPF(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); ++i)
#define REPIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); i+=(s))
#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); --i>=CONCAT(i, $);)
#define REPRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l)-1)/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); (i-=(s)))
#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)
#define FORO(i,n) for(int i=0, CONCAT(i, $)=static_cast<int>(n); i<=CONCAT(i, $); ++i)
#define FORI(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); ++i)
#define FORIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); i+=(s))
#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); i>=CONCAT(i, $); --i)
#define FORRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l))/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); i-=(s))
#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)
#define ITR1(e0,v) for(const auto &e0 : (v))
#define ITRP1(e0,v) for(auto e0 : (v))
#define ITRR1(e0,v) for(auto &e0 : (v))
#define ITR2(e0,e1,v) for(const auto [e0, e1] : (v))
#define ITRP2(e0,e1,v) for(auto [e0, e1] : (v))
#define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v))
#define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v))
#define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v))
#define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v))
#define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v))
#define ITR5(e0,e1,e2,e3,e4,v) for(const auto [e0, e1, e2, e3, e4] : (v))
#define ITRP5(e0,e1,e2,e3,e4,v) for(auto [e0, e1, e2, e3, e4] : (v))
#define ITRR5(e0,e1,e2,e3,e4,v) for(auto &[e0, e1, e2, e3, e4] : (v))
#define ITR(...) $OVERLOAD6(__VA_ARGS__, ITR5, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD6(__VA_ARGS__, ITRP5, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD6(__VA_ARGS__, ITRR5, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
/* [end]: snippet/iterations.hpp*/
/* [begin]: internal/dev_env.hpp */
#ifdef LOCAL_JUDGE
inline constexpr bool DEV_ENV = true; inline constexpr bool NO_EXCEPT = false;
#else
inline constexpr bool DEV_ENV = false; inline constexpr bool NO_EXCEPT = true;
#endif
#if __cplusplus >= 202100L
#define CPP20 true
#define CPP23 true
#elif __cplusplus >= 202002L
#define CPP20 true
#define CPP23 false
#else
#define CPP20 false
#define CPP23 false
#endif
/* [end]: internal/dev_env.hpp*/
/* [begin]: internal/types.hpp */
namespace uni { namespace internal { using size_t = std::int64_t; using int128_t = __int128_t; using uint128_t = __uint128_t; } }
/* [end]: internal/types.hpp*/
/* [begin]: internal/concepts.hpp */
#include <concepts>
#include <limits>
#include <functional>
namespace uni { namespace internal { template<class R, class T> concept convertibel_range = std::convertible_to<std::ranges::range_value_t<R>, T>; template<class T, class V> concept item_or_convertible_range = std::convertible_to<T, V> || convertibel_range<T, V>; template<class Structure> concept available = requires () { typename Structure; }; template< template<class...> class Structure, class... TemplateParameters > concept available_with = available<Structure<TemplateParameters...>>; template<class T> concept arithmetic = std::is_arithmetic_v<T>; template<class T> concept floating_point = std::is_floating_point_v<T>; template<class T> concept pointer = std::is_pointer_v<T>; template<class T> concept structural = std::is_class_v<T>; template<class Large, class Small> concept has_double_digits_of = (std::numeric_limits<Large>::digits == 2 * std::numeric_limits<Small>::digits); template<class Large, class Small> concept has_more_digits_than = (std::numeric_limits<Large>::digits > std::numeric_limits<Small>::digits); template<class Large, class Small> concept has_or_more_digits_than = (std::numeric_limits<Large>::digits >= std::numeric_limits<Small>::digits); template<class T> concept has_static_zero = requires { T::zero; }; template<class T> concept has_static_one = requires { T::one; }; template<class L, class R = L> concept weakly_bitand_calcurable = requires (L lhs, R rhs) { lhs & rhs; }; template<class L, class R = L> concept weakly_bitor_calcurable = requires (L lhs, R rhs) { lhs | rhs; }; template<class L, class R = L> concept weakly_bitxor_calcurable = requires (L lhs, R rhs) { lhs ^ rhs; }; template<class L, class R = L> concept weakly_addable = requires (L lhs, R rhs) { lhs + rhs; }; template<class L, class R = L> concept weakly_subtractable = requires (L lhs, R rhs) { lhs - rhs; }; template<class L, class R = L> concept weakly_multipliable = requires (L lhs, R rhs) { lhs * rhs; }; template<class L, class R = L> concept weakly_divisable = requires (L lhs, R rhs) { lhs / rhs; }; template<class L, class R = L> concept weakly_remainder_calculable = requires (L lhs, R rhs) { lhs % rhs; }; template<class L, class R = L> concept weakly_bitand_assignable = requires (L lhs, R rhs) { lhs += rhs; }; template<class L, class R = L> concept weakly_bitor_assignable = requires (L lhs, R rhs) { lhs |= rhs; }; template<class L, class R = L> concept weakly_bitxor_assignable = requires (L lhs, R rhs) { lhs ^= rhs; }; template<class L, class R = L> concept weakly_addition_assignable = requires (L lhs, R rhs) { lhs += rhs; }; template<class L, class R = L> concept weakly_subtraction_assignable = requires (L lhs, R rhs) { lhs -= rhs; }; template<class L, class R = L> concept weakly_multipliation_assignalbe = requires (L lhs, R rhs) { lhs *= rhs; }; template<class L, class R = L> concept weakly_division_assignable = requires (L lhs, R rhs) { lhs /= rhs; }; template<class L, class R = L> concept weakly_remainder_assignable = requires (L lhs, R rhs) { lhs /= rhs; }; template<class L, class R = L> concept bitand_calculable = weakly_bitand_calcurable<L, R> && weakly_bitand_calcurable<std::invoke_result_t<std::bit_and<>&, L, R>, R> && weakly_bitand_calcurable<L, std::invoke_result_t<std::bit_and<>&, L, R>> && weakly_bitand_calcurable<std::invoke_result_t<std::bit_and<>&, L, R>, std::invoke_result_t<std::bit_and<>&, L, R>>; template<class L, class R = L> concept bitor_calculable = weakly_bitor_calcurable<L, R> && weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, R> && weakly_bitor_calcurable<L, std::invoke_result_t<std::bit_or<>&, L, R>> && weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, std::invoke_result_t<std::bit_or<>&, L, R>>; template<class L, class R = L> concept bitxor_calculable = weakly_bitxor_calcurable<L, R> && weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, R> && weakly_bitxor_calcurable<L, std::invoke_result_t<std::bit_xor<>&, L, R>> && weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, std::invoke_result_t<std::bit_xor<>&, L, R>>; template<class L, class R = L> concept addable = weakly_addable<L, R> && weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, R> && weakly_addable<L, std::invoke_result_t<std::plus<>&, L, R>> && weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, std::invoke_result_t<std::plus<>&, L, R>>; template<class L, class R = L> concept subtractable = weakly_subtractable<L, R> && weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, R> && weakly_subtractable<L, std::invoke_result_t<std::minus<>&, L, R>> && weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, std::invoke_result_t<std::minus<>&, L, R>>; template<class L, class R = L> concept multipliable = weakly_multipliable<L, R> && weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, R> && weakly_multipliable<L, std::invoke_result_t<std::multiplies<>&, L, R>> && weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, std::invoke_result_t<std::multiplies<>&, L, R>>; template<class L, class R = L> concept divisable = weakly_divisable<L, R> && weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, R> && weakly_divisable<L, std::invoke_result_t<std::divides<>&, L, R>> && weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, std::invoke_result_t<std::divides<>&, L, R>>; template<class L, class R = L> concept remainder_calculable = weakly_remainder_calculable<L, R> && weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, R> && weakly_remainder_calculable<L, std::invoke_result_t<std::modulus<>&, L, R>> && weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, std::invoke_result_t<std::modulus<>&, L, R>>; template<class L, class R = L> concept bitand_assignable = weakly_bitand_assignable<L, R> && weakly_bitand_assignable<std::invoke_result_t<std::bit_and<>&, L, R>, R> && weakly_bitand_assignable<L, std::invoke_result_t<std::bit_and<>&, L, R>> && weakly_bitand_assignable<std::invoke_result_t<std::bit_and<>&, L, R>, std::invoke_result_t<std::bit_and<>&, L, R>>; template<class L, class R = L> concept bitor_assignable = weakly_bitor_calcurable<L, R> && weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, R> && weakly_bitor_calcurable<L, std::invoke_result_t<std::bit_or<>&, L, R>> && weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, std::invoke_result_t<std::bit_or<>&, L, R>>; template<class L, class R = L> concept bitxor_assignable = weakly_bitxor_calcurable<L, R> && weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, R> && weakly_bitxor_calcurable<L, std::invoke_result_t<std::bit_xor<>&, L, R>> && weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, std::invoke_result_t<std::bit_xor<>&, L, R>>; template<class L, class R = L> concept addition_assignable = weakly_addition_assignable<L, R> && weakly_addition_assignable<std::remove_cvref_t<std::invoke_result_t<std::plus<>&, L, R>>, R> && weakly_addition_assignable<L, std::invoke_result_t<std::plus<>&, L, R>> && weakly_addition_assignable<std::remove_cvref_t<std::invoke_result_t<std::plus<>&, L, R>>, std::invoke_result_t<std::plus<>&, L, R>>; template<class L, class R = L> concept subtraction_assignable = weakly_subtraction_assignable<L, R> && weakly_subtraction_assignable<std::remove_cvref_t<std::invoke_result_t<std::minus<>&, L, R>>, R> && weakly_subtraction_assignable<L, std::invoke_result_t<std::minus<>&, L, R>> && weakly_subtraction_assignable<std::remove_cvref_t<std::invoke_result_t<std::minus<>&, L, R>>, std::invoke_result_t<std::minus<>&, L, R>>; template<class L, class R = L> concept multipliation_assignalbe = weakly_multipliation_assignalbe<L, R> && weakly_multipliation_assignalbe<std::remove_cvref_t<std::invoke_result_t<std::multiplies<>&, L, R>>, R> && weakly_multipliation_assignalbe<L, std::invoke_result_t<std::multiplies<>&, L, R>> && weakly_multipliation_assignalbe<std::remove_cvref_t<std::invoke_result_t<std::multiplies<>&, L, R>>, std::invoke_result_t<std::multiplies<>&, L, R>>; template<class L, class R = L> concept division_assignable = weakly_division_assignable<L, R> && weakly_division_assignable<std::remove_cvref_t<std::invoke_result_t<std::divides<>&, L, R>>, R> && weakly_division_assignable<L, std::invoke_result_t<std::divides<>&, L, R>> && weakly_division_assignable<std::remove_cvref_t<std::invoke_result_t<std::divides<>&, L, R>>, std::invoke_result_t<std::divides<>&, L, R>>; template<class L, class R = L> concept remainder_assignable = weakly_remainder_assignable<L, R> && weakly_remainder_assignable<std::remove_cvref_t<std::invoke_result_t<std::modulus<>&, L, R>>, R> && weakly_remainder_assignable<L, std::invoke_result_t<std::modulus<>&, L, R>> && weakly_remainder_assignable<std::remove_cvref_t<std::invoke_result_t<std::modulus<>&, L, R>>, std::invoke_result_t<std::modulus<>&, L, R>>; template<class T> concept weakly_incrementable = std::movable<T> && requires (T v) { { ++v } -> std::same_as<T&>; v++; }; template<class T> concept weakly_decrementable = std::movable<T> && requires (T v) { { --v } -> std::same_as<T&>; v--; }; template<class T> concept incrementable = std::regular<T> && weakly_incrementable<T> && requires (T v) { { v++ } -> std::same_as<T>; }; template<class T> concept decrementable = std::regular<T> && weakly_decrementable<T> && requires (T v) { { v-- } -> std::same_as<T>; }; template<class L, class R = L> concept weakly_arithmetic_operable = weakly_addable<L, R> && weakly_subtractable<L, R> && weakly_multipliable<L, R> && weakly_divisable<L, R>; template<class L, class R = L> concept weakly_arithmetic_operation_assignable = weakly_addition_assignable<L, R> && weakly_subtraction_assignable<L, R> && weakly_multipliation_assignalbe<L, R> && weakly_division_assignable<L, R>; template<class L, class R = L> concept arithmetic_operable = weakly_arithmetic_operable<L, R> && addable<L, R> && subtractable<L, R> && multipliable<L, R> && divisable<L, R>; template<class L, class R = L> concept arithmetic_operation_assignable = weakly_arithmetic_operation_assignable<L, R> && addition_assignable<L, R> && subtraction_assignable<L, R> && multipliation_assignalbe<L, R> && division_assignable<L, R>; template<class T> concept unary_addable = requires (T v) { { +v } -> std::same_as<T>; }; template<class T> concept unary_subtractable = requires (T v) { { -v } -> std::same_as<T>; }; template<class T> concept numeric = std::regular<T> && arithmetic_operable<T> && arithmetic_operation_assignable<T> && weakly_incrementable<T> && unary_addable<T> && unary_subtractable<T>; } }
/* [end]: internal/concepts.hpp*/
/* [begin]: numeric/internal/mod.hpp */
namespace uni { template<class T, class R> requires internal::remainder_calculable<T, R> && internal::subtractable<T, R> && internal::unary_subtractable<T> inline T mod(T x, const R& r) noexcept(NO_EXCEPT) { if(x >= 0) return x % r; x = -x % r; if(x != 0) x = r - x; return x; } }
/* [end]: numeric/internal/mod.hpp*/
/* [begin]: iterable/internal/operation_base.hpp */
#include <iterator>
#include <sstream>
#include <numeric>
/* [begin]: internal/exception.hpp */
namespace uni { namespace internal { template<class... T> inline constexpr bool EXCEPTION_ON_TYPE = false; template<auto T> inline constexpr bool EXCEPTION_ON_VALUE = false; } }
/* [end]: internal/exception.hpp*/
namespace uni { template<std::input_iterator I, std::sentinel_for<I> S> std::string join(I first, S last, const char* sep = "") noexcept(NO_EXCEPT) { if(first == last) return ""; std::ostringstream res; while(true) { res << *first; std::ranges::advance(first, 1); if(first == last) break; res << sep; } return res.str(); } template<std::ranges::input_range R> std::string join(R&& range, const char* sep = "") noexcept(NO_EXCEPT) { return join(ALL(range), sep); } template<class I, class T = std::iter_value_t<I>> requires std::sentinel_for<I, I> T sum(I first, I last, const T& base = T()) noexcept(NO_EXCEPT) { return std::accumulate(first, last, base); } template<std::ranges::input_range R, class T = std::ranges::range_value_t<R>> auto sum(R&& range, T base = T()) noexcept(NO_EXCEPT) { auto&& r = range | std::views::common; return sum(ALL(r), base); } }
/* [end]: iterable/internal/operation_base.hpp*/
#define UNI_ADVANCED_CONTAINER_OPERATOR(op_assign, op, concepts) auto& operator op_assign(const value_type& v) noexcept(NO_EXCEPT) requires concepts<value_type> { if constexpr(concepts<Base, value_type>) { this->Base::operator op_assign(v); } else { REP(itr, ALL(*this)) *itr op_assign v; } return *this; } auto& operator op_assign(const advanced_container& rhs) noexcept(NO_EXCEPT) requires concepts<value_type> { if constexpr(concepts<Base>) { this->Base::operator op_assign(*rhs._base()); } else { auto itr = std::ranges::begin(*this), rhs_itr = std::ranges::begin(rhs); auto end = std::ranges::end(*this); for(; itr != end; ++itr, ++rhs_itr) { *itr op_assign *rhs_itr; } } return *this; } template<class T = value_type> requires concepts<value_type> && (std::convertible_to<T, value_type> || std::same_as<T, advanced_container>) friend auto operator op(advanced_container lhs, const T& rhs) noexcept(NO_EXCEPT) { return lhs op_assign rhs; } template<class T = value_type> requires concepts<value_type> && std::convertible_to<T, value_type> friend auto operator op(const T& lhs, advanced_container rhs) noexcept(NO_EXCEPT) { return advanced_container(rhs.size(), lhs) op_assign rhs; }
namespace uni { namespace internal { template<class Base> struct advanced_container : Base { private: inline Base* _base() noexcept(NO_EXCEPT) { return static_cast<Base*>(this); } inline const Base* _base() const noexcept(NO_EXCEPT) { return static_cast<const Base*>(this); } public: using Base::Base; advanced_container(const Base& base) : Base(base) {} using size_type = decltype(std::ranges::size(std::declval<Base>())); using value_type = Base::value_type; inline auto ssize() const noexcept(NO_EXCEPT) { return std::ranges::ssize(*this->_base()); } inline const auto& operator[](internal::size_t p) const noexcept(NO_EXCEPT) { p = p < 0 ? p + this->size() : p; assert(0 <= p && p < this->ssize()); return this->Base::operator[](p); } inline auto& operator[](internal::size_t p) noexcept(NO_EXCEPT) { p = p < 0 ? p + this->size() : p; assert(0 <= p && p < this->ssize()); return this->Base::operator[](p); } inline auto& fill(const value_type& v) noexcept(NO_EXCEPT) { std::ranges::fill(*this, v); return *this; } inline auto& swap(const size_type i, const size_type j) noexcept(NO_EXCEPT) { std::swap(this->operator[](i), this->operator[](j)); return *this; } inline auto& sort() noexcept(NO_EXCEPT) { std::ranges::sort(*this); return *this; } template<class F> inline auto& sort(F&& f) noexcept(NO_EXCEPT) { std::ranges::sort(*this, std::forward<F>(f)); return *this; } inline auto& stable_sort() noexcept(NO_EXCEPT) { std::ranges::stable_sort(*this); return *this; } template<class F> inline auto& stable_sort(F&& f) noexcept(NO_EXCEPT) { std::ranges::stable_sort(*this, std::forward<F>(f)); return *this; } inline auto& reverse() noexcept(NO_EXCEPT) { std::ranges::reverse(*this); return *this; } inline auto count(const value_type& v) const noexcept(NO_EXCEPT) { return std::ranges::count(*this, v); } inline auto contains(const value_type& v) const noexcept(NO_EXCEPT) { return this->count(v) > 0; } template<class F> inline auto count_if(F&& f) const noexcept(NO_EXCEPT) { return std::ranges::count_if(*this, std::forward<F>(f)); } inline auto& resize(const size_type k) noexcept(NO_EXCEPT) { this->Base::resize(k); return *this; } inline auto& resize(const size_type k, const value_type& v) noexcept(NO_EXCEPT) { this->Base::resize(k, v); return *this; } template<class F> inline auto& shuffle(F&& f) noexcept(NO_EXCEPT) { std::ranges::shuffle(*this, std::forward<F>(f)); return *this; } inline auto& unique() noexcept(NO_EXCEPT) { const auto rest = std::ranges::unique(*this); this->erase(ALL(rest)); return *this; } template<class T> inline auto binary_search(T&& v) const noexcept(NO_EXCEPT) { return std::ranges::binary_search(*this, std::forward<T>(v)); } template<class T> inline auto lower_bound(T&& v) const noexcept(NO_EXCEPT) { return std::ranges::lower_bound(*this, std::forward<T>(v)); } template<class T> inline auto upper_bound(T&& v) const noexcept(NO_EXCEPT) { return std::ranges::upper_bound(*this, std::forward<T>(v)); } template<class T> inline auto find(T&& v) const noexcept(NO_EXCEPT) { return std::ranges::find(*this, std::forward<T>(v)); } template<class T> inline auto index(T&& v) const noexcept(NO_EXCEPT) { return this->find(std::forward<T>(v)) - this->begin(); } inline auto join(const char* sep = "") const noexcept(NO_EXCEPT) { return uni::join(*this, sep); } inline auto sum() const noexcept(NO_EXCEPT) { return uni::sum(*this); } inline auto max() const noexcept(NO_EXCEPT) { return std::ranges::max(*this->_base()); } inline auto min() const noexcept(NO_EXCEPT) { return std::ranges::min(*this); } inline auto begin() noexcept(NO_EXCEPT) { return std::ranges::begin(*this->_base()); } inline auto begin() const noexcept(NO_EXCEPT) { return std::ranges::begin(*this->_base()); } inline auto end() noexcept(NO_EXCEPT) { return std::ranges::end(*this->_base()); } inline auto end() const noexcept(NO_EXCEPT) { return std::ranges::end(*this->_base()); } UNI_ADVANCED_CONTAINER_OPERATOR(+=, +, internal::weakly_addition_assignable) UNI_ADVANCED_CONTAINER_OPERATOR(-=, -, internal::weakly_subtraction_assignable) UNI_ADVANCED_CONTAINER_OPERATOR(*=, *, internal::weakly_multipliation_assignalbe) UNI_ADVANCED_CONTAINER_OPERATOR(/=, /, internal::weakly_division_assignable) UNI_ADVANCED_CONTAINER_OPERATOR(%=, %, internal::weakly_remainder_assignable) UNI_ADVANCED_CONTAINER_OPERATOR(&=, &, internal::weakly_bitand_assignable) UNI_ADVANCED_CONTAINER_OPERATOR(|=, |, internal::weakly_bitor_assignable) UNI_ADVANCED_CONTAINER_OPERATOR(^=, ^, internal::weakly_bitxor_assignable) }; } }
#undef UNI_ADVANCED_CONTAINER_OPERATOR
/* [end]: adaptor/internal/advanced_container.hpp*/
namespace uni { using string = internal::advanced_container<std::string>; } namespace std { template<> struct hash<uni::string> { inline auto operator()(const uni::string& key) const noexcept(NO_EXCEPT) { return std::hash<std::string>{}(static_cast<std::string>(key)); } }; }
/* [end]: adaptor/string.hpp*/
#if __GNUG__ >= 13
# define UNI_CONSTEXPR_STD_STRING constexpr std::string
# define UNI_CONSTEXPR_STRING constexpr uni::string
#else
# define UNI_CONSTEXPR_STD_STRING const std::string
# define UNI_CONSTEXPR_STRING const uni::string
#endif
/* [end]: macro/internal/compatibility.hpp*/
/* [begin]: snippet/internal/types.hpp */
namespace uni { using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t;
#ifdef __GNUC__
using i128 = __int128_t; using u128 = __uint128_t; using f128 = __float128;
#endif
using uint = unsigned; using ll = long long; using ull = unsigned long long; using ld = long double; }
/* [end]: snippet/internal/types.hpp*/
namespace uni { constexpr char LN = '\n'; constexpr char SPC = ' '; UNI_CONSTEXPR_STRING DIRECTIONS = "URDL"; constexpr std::pair<int,int> DIRS4[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; constexpr std::pair<int,int> DIRS4P[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, { 0, 0 } }; constexpr std::pair<int,int> DIRS8[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } }; constexpr std::pair<int,int> DIRS8P[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 }, { 0, 0 } }; template<class T> using spair = std::pair<T,T>; template<class T> using priority_queue_rev = std::priority_queue<T, std::vector<T>, std::greater<T>>; } namespace std { using bit_reference = std::vector<bool>::reference; bit_reference operator |= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a | b; } bit_reference operator &= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a & b; } }
/* [end]: snippet/aliases.hpp*/

// #include "adaptor/io.hpp"
/* [begin]: template/debug.hpp */
#ifdef LOCAL_JUDGE
#define DEBUGGER_ENABLED
#define DEBUGGER_COLORED_OUTPUT 1
#endif
/* [begin]: debugger/debug.hpp */
#include <iostream>
#include <string_view>
#include <array>
#include <cstring>
#include <bitset>
#include <deque>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <typeinfo>
#include <cxxabi.h>
/* [begin]: numeric/int128.hpp */
#include <cctype>
namespace std { template<class C, class S> auto& operator>>(std::basic_istream<C, S>& in, uni::i128& v) noexcept(NO_EXCEPT) { std::string str; in >> str; v = 0; bool negative = (str[0] == '-'); REP(d, std::ranges::next(str.begin(), negative), str.end()) { assert(std::isdigit(*d)); v = v * 10 + *d - '0'; } if(negative) v *= -1; return in; } template<class C, class S> auto& operator>>(std::basic_istream<C, S>& in, uni::u128& v) noexcept(NO_EXCEPT) { std::string str; in >> str; v = 0U; assert(str[0] != '-'); REP(d, str.begin(), str.end()) { assert(std::isdigit(*d)); v = v * 10U + *d - '0'; } return in; } template<class C, class S> auto& operator<<(std::basic_ostream<C, S>& out, uni::i128 v) noexcept(NO_EXCEPT) { if(v == 0) return out << 0; if(v < 0) out << '-', v *= -1; std::string str; while(v > 0) str += static_cast<char>(v%10) + '0', v /= 10; std::reverse(str.begin(), str.end()); return out << str; } template<class C, class S> auto& operator<<(std::basic_ostream<C, S>& out, uni::u128 v) noexcept(NO_EXCEPT) { if(v == 0) return out << 0U; std::string str; while(v > 0) str += static_cast<char>(v%10U) + '0', v /= 10U; std::reverse(str.begin(), str.end()); return out << str; } }
/* [end]: numeric/int128.hpp*/
/* [begin]: internal/type_traits.hpp */
namespace uni { namespace internal { template<class... Ts> struct tuple_or_pair { using type = std::tuple<Ts...>; }; template<class T, class U> struct tuple_or_pair<T,U> { using type = std::pair<T, U>; }; template <class... Ts> using tuple_or_pair_t = typename tuple_or_pair<Ts...>::type; template<class T> constexpr std::underlying_type_t<T> to_underlying(const T& v) noexcept(NO_EXCEPT) { return static_cast<std::underlying_type_t<T>>(v); } template<class T, class... Ts> using are_same = std::conjunction<std::is_same<T, Ts>...>; template<class T, class... Ts> inline constexpr bool are_same_v = are_same<T, Ts...>::value; template<class T, class... Ts> using is_same_as_any_of = std::disjunction<std::is_same<T, Ts>...>; template<class T, class... Ts> inline constexpr bool is_same_as_any_of_v = is_same_as_any_of<T, Ts...>::value; template<class T, class... Ts> concept same_as_any_of = is_same_as_any_of_v<T, Ts...>; template<class Base, class... Derived> using is_base_of_all = std::conjunction<std::is_base_of<Base, Derived>...>; template<class Base, class... Derived> inline constexpr bool is_base_of_all_v = is_base_of_all<Base, Derived...>::value; template<class Base, class... Derived> using is_base_of_any = std::disjunction<std::is_base_of<Base, Derived>...>; template<class Base, class... Derived> inline constexpr bool is_base_of_any_v = is_base_of_any<Base, Derived...>::value; template<class T> struct remove_cvref { using type = typename std::remove_cv_t<std::remove_reference_t<T>>; }; template<class T> using remove_cvref_t = typename remove_cvref<T>::type; template<class T> struct literal_operator { static constexpr const char* value = ""; }; template<> struct literal_operator<unsigned> { static constexpr const char* value = "U"; }; template<> struct literal_operator<long> { static constexpr const char* value = "L"; }; template<> struct literal_operator<unsigned long> { static constexpr const char* value = "UL"; }; template<> struct literal_operator<long long> { static constexpr const char* value = "LL"; }; template<> struct literal_operator<unsigned long long> { static constexpr const char* value = "ULL"; }; template<> struct literal_operator<float> { static constexpr const char* value = "F"; }; template<> struct literal_operator<double> { static constexpr const char* value = "D"; }; template<> struct literal_operator<long double> { static constexpr const char* value = "LD"; };
#ifdef __SIZEOF_INT128__
template<> struct literal_operator<__int128_t> { static constexpr const char* value = "LLL"; }; template<> struct literal_operator<__uint128_t> { static constexpr const char* value = "ULLL"; };
#endif
template<class T> inline constexpr auto literal_operator_v = literal_operator<T>::value; template <std::size_t N, typename... Types> using nth_type_t = std::tuple_element_t<N, std::tuple<Types...>>; template<template <class...> class, class> struct is_template_of : std::false_type {}; template<template <class...> class Template, class... Args> struct is_template_of<Template, Template<Args...>> : std::true_type {}; template<template <class...> class Template, class Type> inline constexpr bool is_template_of_v = is_template_of<Template, Type>::value; template<class Type, template <class...> class Template> concept substituted_from = is_template_of_v<Template, Type>; template<template <class...> class Base, class Derived> struct _is_basic_tempalte_of { template<class... Ts> static constexpr std::true_type test(const Base<Ts...> *); static constexpr std::false_type test(...); using type = decltype(test(std::declval<Derived*>())); }; template<template <class...> class Base, class Derived> using is_basic_tempalte_of = _is_basic_tempalte_of<Base, Derived>::type; template<template <class...> class Base, class Derived> inline constexpr bool is_basic_tempalte_of_v = is_basic_tempalte_of<Base, Derived>::value; template<class Derived, template <class...> class Base> concept derived_from_template = is_basic_tempalte_of_v<Base, Derived>; template<class T> struct is_loggable { template<class U> static constexpr auto External(U &&v) -> decltype(_debug(v), std::true_type()); static constexpr std::false_type External(...); template<class U> static constexpr auto Member(U &&v) -> decltype(v._debug(), std::true_type()); static constexpr std::false_type Member(...); static constexpr bool value = ( decltype(External(std::declval<T>()))::value || decltype(Member(std::declval<T>()))::value ); }; template<class T> inline constexpr auto is_loggable_v = is_loggable<T>::value; template<class T> concept loggable = is_loggable_v<T>; template<class T> struct _has_iterator { template<class U> static constexpr auto ADL(U &&v) -> decltype(begin(v), end(v), std::true_type()); static constexpr std::false_type ADL(...); template<class U> static constexpr auto STL(U &&v) -> decltype(std::begin(v), std::end(v), std::true_type()); static constexpr std::false_type STL(...); template<class U> static constexpr auto Member(U &&v) -> decltype(v.begin(), v.end(), std::true_type()); static constexpr std::false_type Member(...); }; template<class T> struct has_iterator { struct ADL : decltype(_has_iterator<T>::ADL(std::declval<T>())) {}; struct STL : decltype(_has_iterator<T>::STL(std::declval<T>())) {}; struct Member : decltype(_has_iterator<T>::Member(std::declval<T>())) {}; static constexpr auto adl_v = ADL::value; static constexpr auto stl_v = STL::value; static constexpr auto member_v = Member::value; }; template<class T> struct is_iterable { static constexpr bool value = has_iterator<T>::adl_v || has_iterator<T>::stl_v || has_iterator<T>::member_v; }; template<class T> inline constexpr auto is_iterable_v = is_iterable<T>::value; template<class T> concept iterable = is_iterable_v<T>; namespace iterator_resolver { template<class T> inline constexpr auto begin(T&& v) noexcept(NO_EXCEPT) { static_assert(is_iterable_v<T>); if constexpr(has_iterator<T>::member_v) { return v.begin(); } else { using std::begin; return begin(std::forward<T>(v)); } } template<class T> inline constexpr auto end(T&& v) noexcept(NO_EXCEPT) { static_assert(is_iterable_v<T>); if constexpr(has_iterator<T>::member_v) { return v.end(); } else { using std::end; return end(std::forward<T>(v)); } } }; template<class C> using iterator_t = decltype(iterator_resolver::begin(std::declval<C&>())); template<class C> using container_size_t = decltype(std::size(std::declval<C&>())); template<bool Const, class T> using maybe_const_t = std::conditional_t<Const, const T, T>; template<class T> using with_ref = T&; template<class T> concept can_reference = requires { typename with_ref<T>; }; } }
/* [end]: internal/type_traits.hpp*/
/* [begin]: internal/resolving_rank.hpp */
namespace uni { namespace internal { template<int P> struct resolving_rank : resolving_rank<P-1> {}; template<> struct resolving_rank<0> {}; } }
/* [end]: internal/resolving_rank.hpp*/
namespace debugger { template<class T> auto _debug (T&& val) -> decltype(val._debug()) { return val._debug(); } std::ostream *cdebug = &std::clog;
#ifdef DEBUGGER_COLORED_OUTPUT
UNI_CONSTEXPR_STD_STRING COLOR_LINE = "\033[3;35m"; UNI_CONSTEXPR_STD_STRING COLOR_IDENTIFIER = "\033[32m"; UNI_CONSTEXPR_STD_STRING COLOR_INIT = "\033[m"; UNI_CONSTEXPR_STD_STRING COLOR_STRING = "\033[33m"; UNI_CONSTEXPR_STD_STRING COLOR_TYPE = "\033[34m"; UNI_CONSTEXPR_STD_STRING COLOR_NUMERIC = "\033[36m"; UNI_CONSTEXPR_STD_STRING COLOR_LITERAL_OPERATOR = "\033[31m";
#else
UNI_CONSTEXPR_STD_STRING COLOR_LINE = ""; UNI_CONSTEXPR_STD_STRING COLOR_IDENTIFIER = ""; UNI_CONSTEXPR_STD_STRING COLOR_INIT = ""; UNI_CONSTEXPR_STD_STRING COLOR_STRING = ""; UNI_CONSTEXPR_STD_STRING COLOR_TYPE = ""; UNI_CONSTEXPR_STD_STRING COLOR_NUMERIC = ""; UNI_CONSTEXPR_STD_STRING COLOR_LITERAL_OPERATOR = "";
#endif
using Brackets = std::pair<std::string, std::string>; template<class T> std::string dump(T&&); template<class T> const std::string get_type_name(T&& val) { const char* const name = typeid(std::forward<T>(val)).name(); int status = -4; char* const demangled_name = abi::__cxa_demangle(name, NULL, NULL, &status); std::string res{name}; if (status == 0) { res = std::string(demangled_name); free(demangled_name); } return COLOR_TYPE + res + COLOR_INIT; } struct debug_t : std::string { using std::string::string; debug_t(const std::string& str) { this->assign(str); } }; template<size_t N, class T> void dump_tuple_impl([[maybe_unused]] T&& val, std::stringstream &res) { if constexpr(N < std::tuple_size_v<std::remove_cvref_t<T>>) { res << dump(std::get<N>(val)); if constexpr(N < std::tuple_size_v<std::remove_cvref_t<T>> - 1) res << ", "; dump_tuple_impl<N + 1>(std::forward<T>(val), res); } } template<std::ranges::input_range R> std::string dump_range_impl(R&& range, const Brackets& brcs = { "[", "]" }, const std::string& spl = ", ") { std::stringstream res; res << brcs.first << " "; auto itr = std::ranges::begin(range); auto end = std::ranges::end(std::forward<R>(range)); while(itr != end) { if(std::ranges::next(itr) == end) res << dump(*itr) << " "; else res << dump(*itr) << spl; ++itr; } res << brcs.second ; return res.str(); } std::string dump_debug_t(debug_t info) { return info; } struct dump_primitive_like { std::string operator()(std::nullptr_t) const { return COLOR_INIT; } template<uni::internal::pointer T> std::string operator()(const T ptr) const { return dump(*ptr); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::basic_string> std::string operator()(T&& val) const { std::stringstream res; res << COLOR_STRING << "`" << val << "`" << COLOR_INIT; return res.str(); } std::string operator()(const char val) const { std::stringstream res; res << COLOR_STRING << "\'" << val << "\'" << COLOR_INIT; return res.str(); } std::string operator()(const char val[]) const { std::stringstream res; res << COLOR_STRING << "\"" << val << "\"" << COLOR_INIT; return res.str(); } std::string operator()(const unsigned char val) const { std::stringstream res; res << COLOR_NUMERIC << static_cast<int>(val) << COLOR_INIT; return res.str(); } std::string operator()(const bool val) const { std::stringstream res; res << COLOR_NUMERIC << (val ? "true" : "false" ) << COLOR_INIT; return res.str(); } template<uni::internal::arithmetic T> std::string operator()(const T val) const { std::stringstream res; res << std::setprecision(std::numeric_limits<T>::digits10) << val; auto str = res.str(); std::string dst = ""; if constexpr(std::integral<T>) { while(str.length() > 3) { dst = ',' + str.substr(str.length() - 3, 3) + dst; str = str.substr(0, str.length() - 3); } } return COLOR_NUMERIC + str + dst + COLOR_LITERAL_OPERATOR + uni::internal::literal_operator_v<T> + COLOR_INIT; }; template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::optional> std::string operator()(T&& val) const { if(val.has_value()) return dump(*val); return COLOR_TYPE + "invalid" + COLOR_INIT; } }; struct dump_bitset { template<std::size_t N> std::string operator()(const std::bitset<N>& val) const { std::stringstream res; res << COLOR_NUMERIC << val.to_string() << COLOR_INIT; return res.str(); } }; struct dump_has_val { template<class T> requires requires (T val) { val.val(); } std::string operator()(T&& val) const { return dump(val.val()); } }; struct dump_iterator { template<std::input_or_output_iterator I> std::string operator()(I&& itr) const { return COLOR_TYPE + "<iterator> " + COLOR_INIT+ dump(*itr); } }; struct dump_wrapper { template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::map> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::multimap> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_map> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_multimap> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::set> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::multiset> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_set> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_multiset> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::valarray> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("[", "]")); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::vector> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("[", "]")); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::deque> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("[", "]")); } template<uni::internal::derived_from_template<std::queue> T> std::string operator()(T val) const { std::vector<typename T::value_type> vec; while(!val.empty()) vec.emplace_back(val.front()), val.pop(); return dump_range_impl(vec, Brackets("<", ">")); } template<uni::internal::derived_from_template<std::stack> T> std::string operator()(T val) const { std::vector<typename T::value_type> vec; while(!val.empty()) vec.emplace_back(val.top()), val.pop(); std::ranges::reverse(vec); return dump_range_impl(vec, Brackets("<", ">")); } template<uni::internal::derived_from_template<std::priority_queue> T> std::string operator()(T val) const { std::vector<typename T::value_type> vec; while(!val.empty()) vec.emplace_back(val.top()), val.pop(); return dump_range_impl(vec, Brackets("<", ">")); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::pair> std::string operator()(T&& val) const { std::stringstream res; res << "( " << dump(val.first) << ", " << dump(val.second) << " )"; return res.str(); } template<class T> requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::tuple> std::string operator()(T&& val) const { std::stringstream res; res << "( "; dump_tuple_impl<0>(val, res); res << " )"; return res.str(); } }; struct dump_range { template<std::ranges::input_range T> std::string operator()(T&& val) const { return dump_range_impl(val); } }; struct dump_loggable { template<uni::internal::loggable T> std::string operator()(T&& val) const { auto res = _debug(val); if constexpr(std::same_as<decltype(res), debug_t>) { return res; } else { return dump(res); } } }; template<class T> std::string dump(T&& val) { if constexpr(std::same_as<std::remove_cvref_t<T>, debug_t>) { return dump_debug_t(std::forward<T>(val)); } if constexpr(std::invocable<dump_primitive_like, T>) { return dump_primitive_like{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_loggable, T>) { return dump_loggable{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_has_val, T>) { return dump_has_val{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_bitset, T>) { return dump_bitset{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_iterator, T>) { return dump_iterator{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_wrapper, T>) { return dump_wrapper{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_range, T>) {; return dump_range{}(std::forward<T>(val)); } return "== dump error =="; } template<class T> void debug(T&& val, const std::string& endl) { *cdebug << dump(val) << endl << std::flush; } constexpr std::string_view WHITESPACES = " \n\r\t\f\v"; std::string ltrim(const std::string &s) { size_t start = s.find_first_not_of(WHITESPACES); return (start == std::string::npos) ? "" : s.substr(start); } std::string rtrim(const std::string &s) { size_t end = s.find_last_not_of(WHITESPACES); return (end == std::string::npos) ? "" : s.substr(0, end + 1); } std::string trim(const std::string &s) { return rtrim(ltrim(s)); } std::vector<std::string> split(const std::string& str) { static constexpr char SEPARATOR = ','; static constexpr char ESCAPE = '\\'; static constexpr std::string_view QUOTATIONS = "\"\'"; static constexpr std::string_view PARENTHESES = "()[]{}<>"; static constexpr auto PARENTHESES_KINDS = std::ranges::size(PARENTHESES); static_assert(PARENTHESES_KINDS % 2 == 0); std::vector<std::string> res = { "" }; bool quoted = false; std::array<int,(PARENTHESES_KINDS / 2)> enclosed = { 0 }; for(auto itr = std::ranges::begin(str); itr != std::ranges::end(str); ++itr) { if(std::ranges::find(QUOTATIONS, *itr) != std::ranges::end(QUOTATIONS)) { if(itr == std::ranges::begin(str) or *std::ranges::prev(itr) != ESCAPE) { quoted ^= true; } } if(const auto found = std::ranges::find(PARENTHESES, *itr); found != std::ranges::end(PARENTHESES)) { if(not quoted) { auto& target = enclosed[std::ranges::distance(std::begin(PARENTHESES), found) / 2]; target = std::max(0, target - static_cast<int>((std::ranges::distance(std::begin(PARENTHESES), found) % 2) * 2) + 1); } } if( not quoted and static_cast<std::size_t>(std::ranges::count(enclosed, 0)) == std::ranges::size(enclosed) and *itr == SEPARATOR ) { res.push_back(""); } else { res.back() += *itr; } } for(auto&& v : res) v = trim(v); return res; } template<class Arg> void raw(std::nullptr_t, Arg&& arg) { *cdebug << std::forward<Arg>(arg) << std::flush; } template<class Arg> void raw(Arg&& arg) { *cdebug << dump(std::forward<Arg>(arg)) << std::flush; } void debug(const std::vector<std::string>, const size_t, const int, const std::string) { debug(nullptr, COLOR_INIT + "\n"); } std::map<std::pair<std::string, int>, int> count; template<class Head, class... Tail> void debug( const std::vector<std::string> args, const size_t idx, const int line, const std::string path, Head&& H, Tail&&... T ) { if(idx == 0) { std::string file = path.substr(path.find_last_of("/") + 1); debug(nullptr, COLOR_LINE + file + " #" + std::to_string(line) + " (" + std::to_string(count[{ file, line }]++) + ")" + COLOR_INIT); } debug(nullptr, "\n - "); const std::string content = dump(H); const std::string type_name = get_type_name(std::forward<Head>(H)); debug(nullptr, COLOR_IDENTIFIER + args[idx] + COLOR_INIT + " : "); debug(nullptr, content); if(type_name.size() + content.size() >= 300) debug(nullptr, "\n "); debug(nullptr, " " + type_name); debug(args, idx + 1, 0, path, std::forward<Tail>(T)...); } }
/* [end]: debugger/debug.hpp*/
#ifdef DEBUGGER_ENABLED
#define debug(...) debugger::debug(debugger::split(#__VA_ARGS__), 0, __LINE__, __FILE__, __VA_ARGS__)
#define debug_(...) do { const std::string file = __FILE__; debugger::raw(nullptr, debugger::COLOR_LINE + file.substr(file.find_last_of("/") + 1) + " #" + std::to_string(__LINE__) + debugger::COLOR_INIT + " "); debugger::raw(__VA_ARGS__); debugger::raw(nullptr, debugger::COLOR_INIT + "\n"); } while(0);
#define DEBUG if constexpr(true)
#else
#define debug(...) ({ ; })
#define debug_(...) ({ ; })
#define DEBUG if constexpr(false)
#endif
/* [end]: template/debug.hpp*/

void solve();

signed main() {
    // debug(__cplusplus);
    int $ = 1;
    // std::cin >> $;
    // while(true) {
        // debug_("Case: #" + std::to_string($++));
    for(auto x : std::views::iota(0, $)) solve();
    // }
    return 0;
}

const std::set<std::array<int, 3>> one = {
    {0, 1, 2},
    {1, 2, 0},
    {2, 0, 1},
};

const std::set<std::array<int, 3>> two = {
    {2, 1, 0},
    {1, 0, 2},
    {0, 2, 1},
};

/* [begin]: template/warnings.hpp */
#pragma GCC diagnostic warning "-Wshadow=local"
/* [end]: template/warnings.hpp*/
void solve() {
    int n; std::cin >> n;
    auto m = 2 * n + 1;
    std::vector<int> a(m); for(auto& x : a) std::cin >> x;
    debug(m, a);

    std::vector<int> b(m - 2);
    REP(i, 2, m) {
        if(one.contains({a[i - 2], a[i - 1], a[i]})) {
            b[i - 2] = 1;
        }
        else if(two.contains({a[i - 2], a[i - 1], a[i]})) {
            b[i - 2] = 2;
        }
        else {
            b[i - 2] = 0;
        }
    }
    debug(b);

    if(b.size() == 1) {
        std::cout << b[0];
        return;
    }

    std::vector<int> c;

    REP(i, m - 2) {
        if(b[i] == 0) {
            if(i % 2 == 0) {
                std::cout << "0\n";
                return;
            }
        }
        else {
            if(i % 2 != 0) {
                std::cout << "0\n";
                return;
            }
            c.push_back(b[i]);
        }
    }
    debug(c);

    int x = c[0];

    REP(i, 1, c.size()) {
        if(c[i] == x) {
            std::cout << "0\n";
            return;
        }
        else {
            x = c[i];
        }
    }

    std::cout << x << "\n";
}
yukicoder

結果

ソースコード
