結果
問題 | No.1650 Moving Coins |
ユーザー | c-- |
提出日時 | 2021-08-26 11:39:54 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 33,274 bytes |
コンパイル時間 | 4,898 ms |
コンパイル使用メモリ | 278,928 KB |
実行使用メモリ | 8,736 KB |
最終ジャッジ日時 | 2024-11-18 08:51:20 |
合計ジャッジ時間 | 9,608 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 23 ms
6,820 KB |
testcase_04 | AC | 18 ms
6,816 KB |
testcase_05 | AC | 22 ms
6,824 KB |
testcase_06 | AC | 25 ms
6,820 KB |
testcase_07 | AC | 24 ms
6,816 KB |
testcase_08 | AC | 45 ms
8,064 KB |
testcase_09 | AC | 43 ms
7,072 KB |
testcase_10 | AC | 46 ms
7,784 KB |
testcase_11 | AC | 46 ms
7,488 KB |
testcase_12 | AC | 37 ms
6,816 KB |
testcase_13 | AC | 38 ms
6,820 KB |
testcase_14 | AC | 43 ms
8,416 KB |
testcase_15 | AC | 33 ms
7,952 KB |
testcase_16 | AC | 47 ms
7,388 KB |
testcase_17 | AC | 48 ms
7,564 KB |
testcase_18 | AC | 51 ms
7,956 KB |
testcase_19 | AC | 60 ms
8,600 KB |
testcase_20 | AC | 62 ms
8,472 KB |
testcase_21 | AC | 62 ms
8,736 KB |
testcase_22 | AC | 60 ms
8,728 KB |
testcase_23 | AC | 62 ms
8,736 KB |
testcase_24 | AC | 23 ms
6,816 KB |
testcase_25 | AC | 24 ms
6,820 KB |
testcase_26 | AC | 38 ms
6,820 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; #include <cmath> #include <complex> #include <regex> #ifndef DBG_MACRO_DBG_H #define DBG_MACRO_DBG_H #if defined(__unix__) || (defined(__APPLE__) && defined(__MACH__)) #define DBG_MACRO_UNIX #elif defined(_MSC_VER) #define DBG_MACRO_WINDOWS #endif #include <algorithm> #include <chrono> #include <ctime> #include <iomanip> #include <ios> #include <iostream> #include <memory> #include <sstream> #include <string> #include <tuple> #include <type_traits> #include <vector> #ifdef DBG_MACRO_UNIX #include <unistd.h> #endif #if __cplusplus >= 201703L #define DBG_MACRO_CXX_STANDARD 17 #elif __cplusplus >= 201402L #define DBG_MACRO_CXX_STANDARD 14 #else #define DBG_MACRO_CXX_STANDARD 11 #endif #if DBG_MACRO_CXX_STANDARD >= 17 #include <optional> #include <variant> #endif namespace dbg { #ifdef DBG_MACRO_UNIX inline bool isColorizedOutputEnabled() { return isatty(fileno(stderr)); } #else inline bool isColorizedOutputEnabled() { return true; } #endif struct time {}; namespace pretty_function { // Compiler-agnostic version of __PRETTY_FUNCTION__ and constants to // extract the template argument in `type_name_impl` #if defined(__clang__) #define DBG_MACRO_PRETTY_FUNCTION __PRETTY_FUNCTION__ static constexpr size_t PREFIX_LENGTH = sizeof("const char *dbg::type_name_impl() [T = ") - 1; static constexpr size_t SUFFIX_LENGTH = sizeof("]") - 1; #elif defined(__GNUC__) && !defined(__clang__) #define DBG_MACRO_PRETTY_FUNCTION __PRETTY_FUNCTION__ static constexpr size_t PREFIX_LENGTH = sizeof("const char* dbg::type_name_impl() [with T = ") - 1; static constexpr size_t SUFFIX_LENGTH = sizeof("]") - 1; #elif defined(_MSC_VER) #define DBG_MACRO_PRETTY_FUNCTION __FUNCSIG__ static constexpr size_t PREFIX_LENGTH = sizeof("const char *__cdecl dbg::type_name_impl<") - 1; static constexpr size_t SUFFIX_LENGTH = sizeof(">(void)") - 1; #else #error "This compiler is currently not supported by dbg_macro." #endif } // namespace pretty_function // Formatting helpers template <typename T> struct print_formatted { static_assert(std::is_integral<T>::value, "Only integral types are supported."); print_formatted(T value, int numeric_base) : inner(value), base(numeric_base) {} operator T() const { return inner; } const char* prefix() const { switch (base) { case 8: return "0o"; case 16: return "0x"; case 2: return "0b"; default: return ""; } } T inner; int base; }; template <typename T> print_formatted<T> hex(T value) { return print_formatted<T>{value, 16}; } template <typename T> print_formatted<T> oct(T value) { return print_formatted<T>{value, 8}; } template <typename T> print_formatted<T> bin(T value) { return print_formatted<T>{value, 2}; } // Implementation of 'type_name<T>()' template <typename T> const char* type_name_impl() { return DBG_MACRO_PRETTY_FUNCTION; } template <typename T> struct type_tag {}; template <int&... ExplicitArgumentBarrier, typename T> std::string get_type_name(type_tag<T>) { namespace pf = pretty_function; std::string type = type_name_impl<T>(); return type.substr(pf::PREFIX_LENGTH, type.size() - pf::PREFIX_LENGTH - pf::SUFFIX_LENGTH); } template <typename T> std::string type_name() { if (std::is_volatile<T>::value) { if (std::is_pointer<T>::value) { return type_name<typename std::remove_volatile<T>::type>() + " volatile"; } else { return "volatile " + type_name<typename std::remove_volatile<T>::type>(); } } if (std::is_const<T>::value) { if (std::is_pointer<T>::value) { return type_name<typename std::remove_const<T>::type>() + " const"; } else { return "const " + type_name<typename std::remove_const<T>::type>(); } } if (std::is_pointer<T>::value) { return type_name<typename std::remove_pointer<T>::type>() + "*"; } if (std::is_lvalue_reference<T>::value) { return type_name<typename std::remove_reference<T>::type>() + "&"; } if (std::is_rvalue_reference<T>::value) { return type_name<typename std::remove_reference<T>::type>() + "&&"; } return get_type_name(type_tag<T>{}); } inline std::string get_type_name(type_tag<short>) { return "short"; } inline std::string get_type_name(type_tag<unsigned short>) { return "unsigned short"; } inline std::string get_type_name(type_tag<long>) { return "long"; } inline std::string get_type_name(type_tag<unsigned long>) { return "unsigned long"; } inline std::string get_type_name(type_tag<std::string>) { return "std::string"; } template <typename T> std::string get_type_name(type_tag<std::vector<T, std::allocator<T>>>) { return "std::vector<" + type_name<T>() + ">"; } template <typename T1, typename T2> std::string get_type_name(type_tag<std::pair<T1, T2>>) { return "std::pair<" + type_name<T1>() + ", " + type_name<T2>() + ">"; } template <typename... T> std::string type_list_to_string() { std::string result; auto unused = {(result += type_name<T>() + ", ", 0)..., 0}; static_cast<void>(unused); #if DBG_MACRO_CXX_STANDARD >= 17 if constexpr (sizeof...(T) > 0) { #else if (sizeof...(T) > 0) { #endif result.pop_back(); result.pop_back(); } return result; } template <typename... T> std::string get_type_name(type_tag<std::tuple<T...>>) { return "std::tuple<" + type_list_to_string<T...>() + ">"; } template <typename T> inline std::string get_type_name(type_tag<print_formatted<T>>) { return type_name<T>(); } // Implementation of 'is_detected' to specialize for container-like types namespace detail_detector { struct nonesuch { nonesuch() = delete; ~nonesuch() = delete; nonesuch(nonesuch const&) = delete; void operator=(nonesuch const&) = delete; }; template <typename...> using void_t = void; template <class Default, class AlwaysVoid, template <class...> class Op, class... Args> struct detector { using value_t = std::false_type; using type = Default; }; template <class Default, template <class...> class Op, class... Args> struct detector<Default, void_t<Op<Args...>>, Op, Args...> { using value_t = std::true_type; using type = Op<Args...>; }; } // namespace detail_detector template <template <class...> class Op, class... Args> using is_detected = typename detail_detector::detector<detail_detector::nonesuch, void, Op, Args...>::value_t; namespace detail { namespace { using std::begin; using std::end; #if DBG_MACRO_CXX_STANDARD < 17 template <typename T> constexpr auto size(const T& c) -> decltype(c.size()) { return c.size(); } template <typename T, std::size_t N> constexpr std::size_t size(const T (&)[N]) { return N; } #else using std::size; #endif } // namespace template <typename T> using detect_begin_t = decltype(detail::begin(std::declval<T>())); template <typename T> using detect_end_t = decltype(detail::end(std::declval<T>())); template <typename T> using detect_size_t = decltype(detail::size(std::declval<T>())); template <typename T> struct is_container { static constexpr bool value = is_detected<detect_begin_t, T>::value && is_detected<detect_end_t, T>::value && is_detected<detect_size_t, T>::value && !std::is_same<std::string, typename std::remove_cv< typename std::remove_reference<T>::type>::type>::value; }; template <typename T> using ostream_operator_t = decltype(std::declval<std::ostream&>() << std::declval<T>()); template <typename T> struct has_ostream_operator : is_detected<ostream_operator_t, T> {}; } // namespace detail // Helper to dbg(…)-print types template <typename T> struct print_type {}; template <typename T> print_type<T> type() { return print_type<T>{}; } // Forward declarations of "pretty_print" template <typename T> inline void pretty_print(std::ostream& stream, const T& value, std::true_type); template <typename T> inline void pretty_print(std::ostream&, const T&, std::false_type); template <typename T> inline typename std::enable_if<!detail::is_container<const T&>::value && !std::is_enum<T>::value, bool>::type pretty_print(std::ostream& stream, const T& value); inline bool pretty_print(std::ostream& stream, const bool& value); inline bool pretty_print(std::ostream& stream, const char& value); template <typename P> inline bool pretty_print(std::ostream& stream, P* const& value); template <typename T, typename Deleter> inline bool pretty_print(std::ostream& stream, std::unique_ptr<T, Deleter>& value); template <typename T> inline bool pretty_print(std::ostream& stream, std::shared_ptr<T>& value); template <size_t N> inline bool pretty_print(std::ostream& stream, const char (&value)[N]); template <> inline bool pretty_print(std::ostream& stream, const char* const& value); template <typename... Ts> inline bool pretty_print(std::ostream& stream, const std::tuple<Ts...>& value); template <> inline bool pretty_print(std::ostream& stream, const std::tuple<>&); template <> inline bool pretty_print(std::ostream& stream, const time&); template <typename T> inline bool pretty_print(std::ostream& stream, const print_formatted<T>& value); template <typename T> inline bool pretty_print(std::ostream& stream, const print_type<T>&); template <typename Enum> inline typename std::enable_if<std::is_enum<Enum>::value, bool>::type pretty_print(std::ostream& stream, Enum const& value); inline bool pretty_print(std::ostream& stream, const std::string& value); #if DBG_MACRO_CXX_STANDARD >= 17 inline bool pretty_print(std::ostream& stream, const std::string_view& value); #endif template <typename T1, typename T2> inline bool pretty_print(std::ostream& stream, const std::pair<T1, T2>& value); #if DBG_MACRO_CXX_STANDARD >= 17 template <typename T> inline bool pretty_print(std::ostream& stream, const std::optional<T>& value); template <typename... Ts> inline bool pretty_print(std::ostream& stream, const std::variant<Ts...>& value); #endif template <typename Container> inline typename std::enable_if<detail::is_container<const Container&>::value, bool>::type pretty_print(std::ostream& stream, const Container& value); // Specializations of "pretty_print" template <typename T> inline void pretty_print(std::ostream& stream, const T& value, std::true_type) { stream << value; } template <typename T> inline void pretty_print(std::ostream&, const T&, std::false_type) { static_assert(detail::has_ostream_operator<const T&>::value, "Type does not support the << ostream operator"); } template <typename T> inline typename std::enable_if<!detail::is_container<const T&>::value && !std::is_enum<T>::value, bool>::type pretty_print(std::ostream& stream, const T& value) { pretty_print(stream, value, typename detail::has_ostream_operator<const T&>::type{}); return true; } inline bool pretty_print(std::ostream& stream, const bool& value) { stream << std::boolalpha << value; return true; } inline bool pretty_print(std::ostream& stream, const char& value) { const bool printable = value >= 0x20 && value <= 0x7E; if (printable) { stream << "'" << value << "'"; } else { stream << "'\\x" << std::setw(2) << std::setfill('0') << std::hex << std::uppercase << (0xFF & value) << "'"; } return true; } template <typename P> inline bool pretty_print(std::ostream& stream, P* const& value) { if (value == nullptr) { stream << "nullptr"; } else { stream << value; } return true; } template <typename T, typename Deleter> inline bool pretty_print(std::ostream& stream, std::unique_ptr<T, Deleter>& value) { pretty_print(stream, value.get()); return true; } template <typename T> inline bool pretty_print(std::ostream& stream, std::shared_ptr<T>& value) { pretty_print(stream, value.get()); stream << " (use_count = " << value.use_count() << ")"; return true; } template <size_t N> inline bool pretty_print(std::ostream& stream, const char (&value)[N]) { stream << value; return false; } template <> inline bool pretty_print(std::ostream& stream, const char* const& value) { stream << '"' << value << '"'; return true; } template <size_t Idx> struct pretty_print_tuple { template <typename... Ts> static void print(std::ostream& stream, const std::tuple<Ts...>& tuple) { pretty_print_tuple<Idx - 1>::print(stream, tuple); stream << ", "; pretty_print(stream, std::get<Idx>(tuple)); } }; template <> struct pretty_print_tuple<0> { template <typename... Ts> static void print(std::ostream& stream, const std::tuple<Ts...>& tuple) { pretty_print(stream, std::get<0>(tuple)); } }; template <typename... Ts> inline bool pretty_print(std::ostream& stream, const std::tuple<Ts...>& value) { stream << "{"; pretty_print_tuple<sizeof...(Ts) - 1>::print(stream, value); stream << "}"; return true; } template <> inline bool pretty_print(std::ostream& stream, const std::tuple<>&) { stream << "{}"; return true; } template <> inline bool pretty_print(std::ostream& stream, const time&) { using namespace std::chrono; const auto now = system_clock::now(); const auto us = duration_cast<microseconds>(now.time_since_epoch()).count() % 1000000; const auto hms = system_clock::to_time_t(now); const std::tm* tm = std::localtime(&hms); stream << "current time = " << std::put_time(tm, "%H:%M:%S") << '.' << std::setw(6) << std::setfill('0') << us; return false; } // Converts decimal integer to binary string template <typename T> std::string decimalToBinary(T n) { const size_t length = 8 * sizeof(T); std::string toRet; toRet.resize(length); for (size_t i = 0; i < length; ++i) { const auto bit_at_index_i = static_cast<char>((n >> i) & 1); toRet[length - 1 - i] = bit_at_index_i + '0'; } return toRet; } template <typename T> inline bool pretty_print(std::ostream& stream, const print_formatted<T>& value) { if (value.inner < 0) { stream << "-"; } stream << value.prefix(); // Print using setbase if (value.base != 2) { stream << std::setw(sizeof(T)) << std::setfill('0') << std::setbase(value.base) << std::uppercase; if (value.inner >= 0) { // The '+' sign makes sure that a uint_8 is printed as a number stream << +value.inner; } else { using unsigned_type = typename std::make_unsigned<T>::type; stream << +(static_cast<unsigned_type>(-(value.inner + 1)) + 1); } } else { // Print for binary if (value.inner >= 0) { stream << decimalToBinary(value.inner); } else { using unsigned_type = typename std::make_unsigned<T>::type; stream << decimalToBinary<unsigned_type>( static_cast<unsigned_type>(-(value.inner + 1)) + 1); } } return true; } template <typename T> inline bool pretty_print(std::ostream& stream, const print_type<T>&) { stream << type_name<T>(); stream << " [sizeof: " << sizeof(T) << " byte, "; stream << "trivial: "; if (std::is_trivial<T>::value) { stream << "yes"; } else { stream << "no"; } stream << ", standard layout: "; if (std::is_standard_layout<T>::value) { stream << "yes"; } else { stream << "no"; } stream << "]"; return false; } template <typename Enum> inline typename std::enable_if<std::is_enum<Enum>::value, bool>::type pretty_print(std::ostream& stream, Enum const& value) { using UnderlyingType = typename std::underlying_type<Enum>::type; stream << static_cast<UnderlyingType>(value); return true; } inline bool pretty_print(std::ostream& stream, const std::string& value) { stream << '"' << value << '"'; return true; } #if DBG_MACRO_CXX_STANDARD >= 17 inline bool pretty_print(std::ostream& stream, const std::string_view& value) { stream << '"' << std::string(value) << '"'; return true; } #endif template <typename T1, typename T2> inline bool pretty_print(std::ostream& stream, const std::pair<T1, T2>& value) { stream << "{"; pretty_print(stream, value.first); stream << ", "; pretty_print(stream, value.second); stream << "}"; return true; } #if DBG_MACRO_CXX_STANDARD >= 17 template <typename T> inline bool pretty_print(std::ostream& stream, const std::optional<T>& value) { if (value) { stream << '{'; pretty_print(stream, *value); stream << '}'; } else { stream << "nullopt"; } return true; } template <typename... Ts> inline bool pretty_print(std::ostream& stream, const std::variant<Ts...>& value) { stream << "{"; std::visit([&stream](auto&& arg) { pretty_print(stream, arg); }, value); stream << "}"; return true; } #endif template <typename Container> inline typename std::enable_if<detail::is_container<const Container&>::value, bool>::type pretty_print(std::ostream& stream, const Container& value) { stream << "{"; const size_t size = detail::size(value); const size_t n = std::min(size_t{10}, size); size_t i = 0; using std::begin; using std::end; for (auto it = begin(value); it != end(value) && i < n; ++it, ++i) { pretty_print(stream, *it); if (i != n - 1) { stream << ", "; } } if (size > n) { stream << ", ..."; stream << " size:" << size; } stream << "}"; return true; } template <typename T, typename... U> struct last { using type = typename last<U...>::type; }; template <typename T> struct last<T> { using type = T; }; template <typename... T> using last_t = typename last<T...>::type; class DebugOutput { public: // Helper alias to avoid obscure type `const char* const*` in signature. using expr_t = const char*; DebugOutput(const char* filepath, int line, const char* function_name) : m_use_colorized_output(isColorizedOutputEnabled()) { std::string path = filepath; const std::size_t path_length = path.length(); if (path_length > MAX_PATH_LENGTH) { path = ".." + path.substr(path_length - MAX_PATH_LENGTH, MAX_PATH_LENGTH); } std::stringstream ss; ss << ansi(ANSI_DEBUG) << "[" << path << ":" << line << " (" << function_name << ")] " << ansi(ANSI_RESET); m_location = ss.str(); } template <typename... T> auto print(std::initializer_list<expr_t> exprs, std::initializer_list<std::string> types, T&&... values) -> last_t<T...> { if (exprs.size() != sizeof...(values)) { std::cerr << m_location << ansi(ANSI_WARN) << "The number of arguments mismatch, please check unprotected comma" << ansi(ANSI_RESET) << std::endl; } return print_impl(exprs.begin(), types.begin(), std::forward<T>(values)...); } private: template <typename T> T&& print_impl(const expr_t* expr, const std::string* type, T&& value) { const T& ref = value; std::stringstream stream_value; const bool print_expr_and_type = pretty_print(stream_value, ref); std::stringstream output; output << m_location; if (print_expr_and_type) { output << ansi(ANSI_EXPRESSION) << *expr << ansi(ANSI_RESET) << " = "; } output << ansi(ANSI_VALUE) << stream_value.str() << ansi(ANSI_RESET); if (print_expr_and_type) { output << " (" << ansi(ANSI_TYPE) << *type << ansi(ANSI_RESET) << ")"; } output << std::endl; std::cerr << output.str(); return std::forward<T>(value); } template <typename T, typename... U> auto print_impl(const expr_t* exprs, const std::string* types, T&& value, U&&... rest) -> last_t<T, U...> { print_impl(exprs, types, std::forward<T>(value)); return print_impl(exprs + 1, types + 1, std::forward<U>(rest)...); } const char* ansi(const char* code) const { if (m_use_colorized_output) { return code; } else { return ANSI_EMPTY; } } const bool m_use_colorized_output; std::string m_location; static constexpr std::size_t MAX_PATH_LENGTH = 20; static constexpr const char* const ANSI_EMPTY = ""; static constexpr const char* const ANSI_DEBUG = "\x1b[02m"; static constexpr const char* const ANSI_WARN = "\x1b[33m"; static constexpr const char* const ANSI_EXPRESSION = "\x1b[36m"; static constexpr const char* const ANSI_VALUE = "\x1b[01m"; static constexpr const char* const ANSI_TYPE = "\x1b[32m"; static constexpr const char* const ANSI_RESET = "\x1b[0m"; }; // Identity function to suppress "-Wunused-value" warnings in DBG_MACRO_DISABLE // mode template <typename T> T&& identity(T&& t) { return std::forward<T>(t); } template <typename T, typename... U> auto identity(T&&, U&&... u) -> last_t<U...> { return identity(std::forward<U>(u)...); } } // namespace dbg #ifndef DBG_MACRO_DISABLE // Force expanding argument with commas for MSVC, ref: // https://stackoverflow.com/questions/35210637/macro-expansion-argument-with-commas // Note that "args" should be a tuple with parentheses, such as "(e1, e2, ...)". #define DBG_IDENTITY(x) x #define DBG_CALL(fn, args) DBG_IDENTITY(fn args) #define DBG_CAT_IMPL(_1, _2) _1##_2 #define DBG_CAT(_1, _2) DBG_CAT_IMPL(_1, _2) #define DBG_16TH_IMPL(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, \ _14, _15, _16, ...) \ _16 #define DBG_16TH(args) DBG_CALL(DBG_16TH_IMPL, args) #define DBG_NARG(...) \ DBG_16TH((__VA_ARGS__, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)) // DBG_VARIADIC_CALL(fn, data, e1, e2, ...) => fn_N(data, (e1, e2, ...)) #define DBG_VARIADIC_CALL(fn, data, ...) \ DBG_CAT(fn##_, DBG_NARG(__VA_ARGS__))(data, (__VA_ARGS__)) // (e1, e2, e3, ...) => e1 #define DBG_HEAD_IMPL(_1, ...) _1 #define DBG_HEAD(args) DBG_CALL(DBG_HEAD_IMPL, args) // (e1, e2, e3, ...) => (e2, e3, ...) #define DBG_TAIL_IMPL(_1, ...) (__VA_ARGS__) #define DBG_TAIL(args) DBG_CALL(DBG_TAIL_IMPL, args) #define DBG_MAP_1(fn, args) DBG_CALL(fn, args) #define DBG_MAP_2(fn, args) fn(DBG_HEAD(args)), DBG_MAP_1(fn, DBG_TAIL(args)) #define DBG_MAP_3(fn, args) fn(DBG_HEAD(args)), DBG_MAP_2(fn, DBG_TAIL(args)) #define DBG_MAP_4(fn, args) fn(DBG_HEAD(args)), DBG_MAP_3(fn, DBG_TAIL(args)) #define DBG_MAP_5(fn, args) fn(DBG_HEAD(args)), DBG_MAP_4(fn, DBG_TAIL(args)) #define DBG_MAP_6(fn, args) fn(DBG_HEAD(args)), DBG_MAP_5(fn, DBG_TAIL(args)) #define DBG_MAP_7(fn, args) fn(DBG_HEAD(args)), DBG_MAP_6(fn, DBG_TAIL(args)) #define DBG_MAP_8(fn, args) fn(DBG_HEAD(args)), DBG_MAP_7(fn, DBG_TAIL(args)) #define DBG_MAP_9(fn, args) fn(DBG_HEAD(args)), DBG_MAP_8(fn, DBG_TAIL(args)) #define DBG_MAP_10(fn, args) fn(DBG_HEAD(args)), DBG_MAP_9(fn, DBG_TAIL(args)) #define DBG_MAP_11(fn, args) fn(DBG_HEAD(args)), DBG_MAP_10(fn, DBG_TAIL(args)) #define DBG_MAP_12(fn, args) fn(DBG_HEAD(args)), DBG_MAP_11(fn, DBG_TAIL(args)) #define DBG_MAP_13(fn, args) fn(DBG_HEAD(args)), DBG_MAP_12(fn, DBG_TAIL(args)) #define DBG_MAP_14(fn, args) fn(DBG_HEAD(args)), DBG_MAP_13(fn, DBG_TAIL(args)) #define DBG_MAP_15(fn, args) fn(DBG_HEAD(args)), DBG_MAP_14(fn, DBG_TAIL(args)) #define DBG_MAP_16(fn, args) fn(DBG_HEAD(args)), DBG_MAP_15(fn, DBG_TAIL(args)) // DBG_MAP(fn, e1, e2, e3, ...) => fn(e1), fn(e2), fn(e3), ... #define DBG_MAP(fn, ...) DBG_VARIADIC_CALL(DBG_MAP, fn, __VA_ARGS__) #define DBG_STRINGIFY_IMPL(x) #x #define DBG_STRINGIFY(x) DBG_STRINGIFY_IMPL(x) #define DBG_TYPE_NAME(x) dbg::type_name<decltype(x)>() #define dbg(...) \ dbg::DebugOutput(__FILE__, __LINE__, __func__) \ .print({DBG_MAP(DBG_STRINGIFY, __VA_ARGS__)}, \ {DBG_MAP(DBG_TYPE_NAME, __VA_ARGS__)}, __VA_ARGS__) #else #define dbg(...) dbg::identity(__VA_ARGS__) #endif // DBG_MACRO_DISABLE #endif // DBG_MACRO_DBG_H // END DEBUG MACRO ////////////////////////////////////////////////////////////// // START MACROS ////////////////////////////////////////////////////////////// #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i <= n; ++i) #define reps(i, s, e) for (ll i = s; i <= e; ++i) #define rrep(i, n) for (ll i = n - 1; 0 <= i; --i) #define rrep1(i, n) for (ll i = n; 1 <= i; --i) #define fore(i, a) for (auto& i : a) #define cina(a) cin >> a; #define cinb(a, b) cin >> a >> b; #define cinc(a, b, c) cin >> a >> b >> c; #define cind(a, b, c, d) cin >> a >> b >> c >> d; #define cine(a, b, c, d, e) cin >> a >> b >> c >> d >> e; #define cendl std::cout << endl; #define pcnt __builtin_popcountll #define forcin(a) \ for (auto& it : a) cin >> it; #define p(ans) std::cout << ans << endl; #define p2(ans, ans2) std::cout << ans << " " << ans2 << endl; #define p3(ans, ans2, ans3) \ std::cout << ans << " " << ans2 << " " << ans3 << endl; #define p4(ans, ans2, ans3, ans4) \ std::cout << ans << " " << ans2 << " " << ans3 << " " << ans4 << endl; #define dd(arg) \ cerr << "\x1b[38;5;39m|\x1b[m " << #arg << " \x1b[38;5;39m= \x1b[m" << arg \ << " \x1b[38;5;39m|\x1b[m " << endl; #define dd2(arg, arg2) \ cerr << "\x1b[38;5;39m|\x1b[m " << #arg << "\x1b[38;5;39m =\x1b[m " << arg \ << " \x1b[38;5;39m|\x1b[m " << #arg2 << "\x1b[38;5;39m =\x1b[m " \ << arg2 << " \x1b[38;5;39m|\x1b[m " << endl; #define dd3(arg, arg2, arg3) \ cerr << "\x1b[38;5;39m|\x1b[m " << #arg << "\x1b[38;5;39m =\x1b[m " << arg \ << " \x1b[38;5;39m|\x1b[m " << #arg2 << "\x1b[38;5;39m =\x1b[m " \ << arg2 << " \x1b[38;5;39m|\x1b[m " << #arg3 \ << "\x1b[38;5;39m =\x1b[m " << arg3 << " \x1b[38;5;39m|\x1b[m " \ << endl; #define dd4(arg, arg2, arg3, arg4) \ cerr << "\x1b[38;5;39m|\x1b[m " << #arg << "\x1b[38;5;39m =\x1b[m " << arg \ << " \x1b[38;5;39m|\x1b[m " << #arg2 << "\x1b[38;5;39m =\x1b[m " \ << arg2 << " \x1b[38;5;39m|\x1b[m " << #arg3 \ << "\x1b[38;5;39m =\x1b[m " << arg3 << " \x1b[38;5;39m|\x1b[m " \ << #arg4 << "\x1b[38;5;39m =\x1b[m " << arg4 \ << " \x1b[38;5;39m|\x1b[m " << endl; #define dl(n, l) \ { \ cerr << "\x1b[38;5;39m|\x1b[m " << #l << "\x1b[38;5;39m =\x1b[m "; \ for (int z = 0; z < n; ++z) { \ if (z == n - 1) { \ cerr << l[z] << " \x1b[38;5;39m|\x1b[m " << endl; \ } else { \ cerr << l[z] << " "; \ } \ } \ }; #define pl(n, l) \ { \ for (int z = 0; z < n; ++z) { \ if (z == n - 1) { \ cout << l[z] << endl; \ } else { \ cout << l[z] << " "; \ } \ } \ }; #define pb push_back #define all(v) v.begin(), v.end() #define allr(v) v.rbegin(), v.rend() #define endl '\n' #define posl(vec, elm) lower_bound(vec.begin(), vec.end(), elm) - vec.begin() #define posu(vec, elm) upper_bound(vec.begin(), vec.end(), elm) - vec.begin() #define uqv(v) \ { \ sort(all(v)); \ v.erase(unique(all(v)), v.end()); \ }; template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template <class T> inline bool pmap(T& mp) { cerr << "| "; for (auto itr = mp.begin(); itr != mp.end(); ++itr) { cerr << "key: " << itr->first << ", val: " << itr->second << " | "; } cerr << endl; return 0; } using ll = long long; using ld = long double; using cp = complex<ld>; using pa = pair<ll, ll>; using tup = tuple<ll, ll, ll>; using vp = vector<pair<ll, ll>>; using vtup = vector<tuple<ll, ll, ll>>; using st = string; using vs = vector<string>; using vc = vector<char>; using vvi = vector<vector<ll>>; using vvc = vector<vector<char>>; using vi = vector<ll>; const ll MOD1 = 1000000007; const ll MOD2 = 998244353; const ll LINF = (1LL << 60); const int INF = (1000000007); const ld EPS = 1e-10; const long double PI = 3.141592653589793238462643383279502884L; // std::cout << fixed << setprecision(15); ll lcm(ll x, ll y) { return ll(x / gcd(x, y)) * y; } bool isprime(ll n) { if (n == 2) return true; if (n < 2 || !(n & 1)) return false; ll i = 3; while (i <= sqrt(n)) { if (n % i == 0) return false; i += 2; } return true; } vi prime_factors(ll n) { ll rem = n; vi p; for (ll i = 2; i * i <= n; i++) { while (rem % i == 0) { rem /= i; p.pb(i); } } if (rem != 1LL) p.pb(rem); return p; } map<ll, int> prime_factorize_count(ll n) { map<ll, int> V; for (ll i = 2; i * i <= n; i++) while (n % i == 0) V[i]++, n /= i; if (n > 1) V[n]++; return V; } ll modpow(ll a, ll n, ll mod) { ll res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } ll nck(ll n, ll k, ll modd) { ll p = 1, q = 1; for (ll i = 0; i < k; i++) { p = p * (n - i) % modd; q = q * (i + 1) % modd; } return p * modpow(q, modd - 2, modd) % modd; } ll dx[4] = {-1, 0, 1, 0}; ll dy[4] = {0, 1, 0, -1}; vector<pa> dydx = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; vi enum_divisors(ll N) { vi res; for (ll i = 1; i * i <= N; ++i) { if (N % i == 0) { res.push_back(i); if (N / i != i) res.push_back(N / i); } } sort(res.begin(), res.end()); return res; } // vp g[100009]; // vector<ll> dijkstra(ll stt) { // priority_queue<pa, vp, greater<pa>> q; // vi dist; // rep1(i, n + 1) dist.pb(INF); // dist[stt] = 0; // q.push(make_pair(0, stt)); // while (!q.empty()) { // int pos = q.top().second; // q.pop(); // rep(i, g[pos].size()) { // ll to = g[pos][i].first; // ll cost = g[pos][i].second; // if (dist[to] > dist[pos] + cost) { // dist[to] = dist[pos] + cost; // q.push(make_pair(dist[to], to)); // } // } // } // return dist; // } const int mod = MOD1; struct mint { ll x; mint(ll x = 0) : x((x % mod + mod) % mod) {} mint operator-() const { return mint(-x); } mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint a) const { return mint(*this) += a; } mint operator-(const mint a) const { return mint(*this) -= a; } mint operator*(const mint a) const { return mint(*this) *= a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t >> 1); a *= a; if (t & 1) a *= *this; return a; } mint inv() const { return pow(mod - 2); } mint& operator/=(const mint a) { return *this *= a.inv(); } mint operator/(const mint a) const { return mint(*this) /= a; } }; istream& operator>>(istream& is, mint& a) { return is >> a.x; } ostream& operator<<(ostream& os, const mint& a) { return os << a.x; } struct combination { vector<mint> fact, ifact; combination(int n) : fact(n + 1), ifact(n + 1) { assert(n < mod); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i; ifact[n] = fact[n].inv(); for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i; } mint operator()(int n, int k) { if (k < 0 || k > n) return 0; return fact[n] * ifact[k] * ifact[n - k]; } }; void init() { cin.tie(0); std::cout.tie(0); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); } void _main(); int main() { init(); _main(); }; ////////////////////////////////////////////////////////////// // https://yukicoder.me/problems/no/1650 ////////////////////////////////////////////////////////////// ll n; ll a[200009], b[200009]; ////////////////////////////////////////////////////////////// void _main() { cina(n); rep(i, n) cina(a[i]); rep(i, n) cina(b[i]); vi l, r; rep(i, n) { if (a[i] <= b[i]) continue; while (a[i] != b[i]) { l.pb(i + 1); --a[i]; } } rrep(i, n) { if (a[i] >= b[i]) continue; while (a[i] != b[i]) { r.pb(i + 1); ++a[i]; } } p((l.size() + r.size())); fore(i, l) p2(i, "L"); fore(i, r) p2(i, "R"); }