shogo-library
競技プログラミング用の C++ ライブラリ
test/aoj/itp2-5-b.test.cpp
- View this file on GitHub
- Last update: 2026-10-13 06:07:05+09:00
- Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_5_B
Depends on
- コンテナに対する関数 (sorted, max, sum など)
(src/base/container_func.hpp)
- 空白区切り出力、iostreamのオーバーロード
(src/base/io.hpp)
- 型特性
(src/base/traits.hpp)
Code
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_5_B"
#include <iostream>
#include <string>
#include <tuple>
#include <vector>
#include "../../src/base/container_func.hpp"
#include "../../src/base/io.hpp"
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
// 価値、重さ、型、日時、名前 (この順の辞書式順序が問題の優先順位と同じ)
std::vector<std::tuple<long long, long long, char, long long, std::string>> items(n);
std::cin >> items; // tuple の vector をまとめて読む
sort(items);
for (const auto& t : items) std::cout << t << '\n'; // tuple を空白区切りで出力
}#line 1 "test/aoj/itp2-5-b.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_5_B"
#include <iostream>
#include <string>
#include <tuple>
#include <vector>
#line 2 "src/base/container_func.hpp"
/**
* @file container_func.hpp
* @brief コンテナに対する関数 (sorted, max, sum など)
*/
#include <algorithm>
#include <cassert>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <numeric>
#line 2 "src/base/traits.hpp"
/**
* @file traits.hpp
* @brief 型特性
*/
#include <cstddef>
#line 10 "src/base/traits.hpp"
#include <set>
#include <type_traits>
#include <utility>
namespace detail {
using std::begin, std::end;
template <class T, class = void>
struct is_range_impl : std::false_type {};
template <class T>
struct is_range_impl<T, std::void_t<decltype(begin(std::declval<T&>()), end(std::declval<T&>()))>> : std::true_type {};
} // namespace detail
template <class T>
struct is_range : detail::is_range_impl<T>::type {};
template <class T>
inline constexpr bool is_range_v = is_range<T>::value;
#define HAS_METHOD(func_name) \
namespace detail { \
template <class T, class = void> \
struct has_##func_name##_impl : std::false_type {}; \
template <class T> \
struct has_##func_name##_impl<T, std::void_t<decltype(std::declval<T>().func_name())>> \
: std::true_type {}; \
} \
template <class T> \
struct has_##func_name : detail::has_##func_name##_impl<T>::type {}; \
template <class T> \
inline constexpr bool has_##func_name##_v = has_##func_name<T>::value;
#define HAS_METHOD_ARG(func_name) \
namespace detail { \
template <class T, typename U, class = void> \
struct has_##func_name##_impl : std::false_type {}; \
template <class T, typename U> \
struct has_##func_name##_impl<T, U, std::void_t<decltype(std::declval<T>().func_name(std::declval<U>()))>> \
: std::true_type {}; \
} \
template <class T, typename U> \
struct has_##func_name : detail::has_##func_name##_impl<T, U>::type {}; \
template <class T, typename U> \
inline constexpr bool has_##func_name##_v = has_##func_name<T, U>::value;
HAS_METHOD(repr)
HAS_METHOD(type_str)
HAS_METHOD(initializer_str)
HAS_METHOD(max)
HAS_METHOD(min)
HAS_METHOD(reversed)
HAS_METHOD(sorted)
HAS_METHOD(sum)
HAS_METHOD(product)
HAS_METHOD(product_xor)
HAS_METHOD_ARG(count)
HAS_METHOD_ARG(find)
HAS_METHOD_ARG(lower_bound)
HAS_METHOD_ARG(upper_bound)
#define ENABLE_IF_T_IMPL(expr) std::enable_if_t<expr, std::nullptr_t> = nullptr
#define ENABLE_IF_T(...) ENABLE_IF_T_IMPL((__VA_ARGS__))
template <class C>
using mem_value_type = typename C::value_type;
template <class C>
using mem_difference_type = typename C::difference_type;
namespace detail {
template <class T, class = void>
struct is_sorted_container_impl : std::false_type {};
template <class T>
struct is_sorted_container_impl<std::set<T>> : std::true_type {};
template <class T>
struct is_sorted_container_impl<std::multiset<T>> : std::true_type {};
} // namespace detail
template <class T>
struct is_sorted_container : detail::is_sorted_container_impl<T>::type {};
template <class T>
inline constexpr bool is_sorted_container_v = is_sorted_container<T>::value;
#line 16 "src/base/container_func.hpp"
#define METHOD_EXPAND(func) \
template <typename T, ENABLE_IF_T(has_##func##_v<T>)> \
inline constexpr auto func(const T &t) -> decltype(t.func()) { \
return t.func(); \
}
#define METHOD_AND_FUNC_ARG_EXPAND(func) \
template <typename T, typename U, ENABLE_IF_T(has_##func##_v<T, U>)> \
inline constexpr auto func(const T &t, const U &u) \
-> decltype(t.func(u)) { \
return t.func(u); \
} \
template <typename T, typename U, ENABLE_IF_T(not has_##func##_v<T, U>)> \
inline constexpr auto func(const T &t, const U &u) \
-> decltype(std::func(t.begin(), t.end(), u)) { \
return std::func(t.begin(), t.end(), u); \
}
METHOD_EXPAND(reversed)
template <class C, ENABLE_IF_T(not has_reversed_v<C>)>
inline constexpr C reversed(C t) {
std::reverse(t.begin(), t.end());
return t;
}
METHOD_EXPAND(sorted)
template <class C, ENABLE_IF_T(not has_sorted_v<C>)>
inline constexpr C sorted(C t, bool reverse = false) {
std::sort(t.begin(), t.end());
if (reverse) std::reverse(t.begin(), t.end());
return t;
}
template <class C, class F, ENABLE_IF_T(not has_sorted_v<C> and std::is_invocable_r_v<bool, F, mem_value_type<C>, mem_value_type<C>>)>
inline constexpr C sorted(C t, F f) {
std::sort(t.begin(), t.end(), f);
return t;
}
template <class C>
inline constexpr void sort(C &t, bool reverse = false) {
std::sort(t.begin(), t.end());
if (reverse) std::reverse(t.begin(), t.end());
}
template <class C, class F, ENABLE_IF_T(std::is_invocable_r_v<bool, F, mem_value_type<C>, mem_value_type<C>>)>
inline constexpr void sort(C &t, F f) {
std::sort(t.begin(), t.end(), f);
}
template <class C, class F, ENABLE_IF_T(std::is_invocable_v<F, mem_value_type<C>>)>
inline constexpr void sort_by_key(C &t, F f) {
std::sort(t.begin(), t.end(), [&](const mem_value_type<C> &left, const mem_value_type<C> &right) {
return f(left) < f(right);
});
}
template <class C>
inline constexpr void reverse(C &t) {
std::reverse(t.begin(), t.end());
}
METHOD_EXPAND(max)
template <class C, ENABLE_IF_T(not has_max_v<C> and is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> max(const C &v) {
assert(v.begin() != v.end());
return *v.rbegin();
}
template <class C, ENABLE_IF_T(not has_max_v<C> and not is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> max(const C &v) {
assert(v.begin() != v.end());
return *std::max_element(v.begin(), v.end());
}
template <typename T>
inline constexpr T max(const std::initializer_list<T> &v) {
return std::max(v);
}
METHOD_EXPAND(min)
template <class C, ENABLE_IF_T(not has_min_v<C> and is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> min(const C &v) {
assert(v.begin() != v.end());
return *v.begin();
}
template <class C, ENABLE_IF_T(not has_min_v<C> and not is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> min(const C &v) {
assert(v.begin() != v.end());
return *std::min_element(v.begin(), v.end());
}
template <typename T>
inline constexpr T min(const std::initializer_list<T> &v) {
return std::min(v);
}
METHOD_EXPAND(sum)
template <class C, ENABLE_IF_T(not has_sum_v<C>)>
inline constexpr mem_value_type<C> sum(const C &v) {
return std::accumulate(v.begin(), v.end(), mem_value_type<C>{});
}
template <typename T>
inline constexpr T sum(const std::initializer_list<T> &v) {
return std::accumulate(v.begin(), v.end(), T{});
}
METHOD_EXPAND(product)
template <class C, ENABLE_IF_T(not has_product_v<C>)>
inline constexpr mem_value_type<C> product(const C &v) {
return std::accumulate(v.begin(), v.end(), mem_value_type<C>{1}, std::multiplies<mem_value_type<C>>());
}
template <typename T>
inline constexpr T product(const std::initializer_list<T> &v) {
return std::accumulate(v.begin(), v.end(), T{1}, std::multiplies<T>());
}
METHOD_EXPAND(product_xor)
template <class C, ENABLE_IF_T(not has_product_xor_v<C>)>
inline constexpr mem_value_type<C> product_xor(const C &v) {
return std::accumulate(v.begin(), v.end(), mem_value_type<C>{0}, std::bit_xor<mem_value_type<C>>());
}
template <typename T>
inline constexpr T product_xor(const std::initializer_list<T> &v) {
return std::accumulate(v.begin(), v.end(), T{0}, std::bit_xor<T>());
}
template <class C>
inline constexpr mem_value_type<C> maximum_subarray(const C &v) {
assert(not v.empty());
auto itr = v.begin();
mem_value_type<C> tmp = *itr++;
mem_value_type<C> res = tmp;
while (itr != v.end()) {
tmp += *itr;
if (tmp < *itr) tmp = *itr;
if (res < tmp) res = tmp;
++itr;
}
return res;
}
template <class C>
inline constexpr mem_value_type<C> maximum_subarray(const C &v, mem_value_type<C> init) {
mem_value_type<C> res = init, tmp = init;
for (const auto &a : v) {
tmp += a;
if (tmp < init) tmp = init;
if (res < tmp) res = tmp;
}
return res;
}
METHOD_AND_FUNC_ARG_EXPAND(count)
METHOD_AND_FUNC_ARG_EXPAND(find)
METHOD_AND_FUNC_ARG_EXPAND(lower_bound)
METHOD_AND_FUNC_ARG_EXPAND(upper_bound)
template <class C, typename T>
inline constexpr bool contains(const C &c, const T &t) {
return find(c, t) != c.end();
}
template <class C>
inline constexpr mem_value_type<C> gcd(const C &v) {
mem_value_type<C> init(0);
for (const auto &e : v) init = std::gcd(init, e);
return init;
}
template <class C>
inline constexpr mem_value_type<C> average(const C &v) {
assert(v.size());
return sum(v) / v.size();
}
template <class C>
inline constexpr mem_value_type<C> median(const C &v) {
assert(not v.empty());
std::vector<size_t> u(v.size());
std::iota(u.begin(), u.end(), 0);
std::sort(u.begin(), u.end(), [&](size_t a, size_t b) {
return v[a] < v[b];
});
if (v.size() & 1) {
return v[u[v.size() / 2]];
}
// C++20
// return std::midpoint(v[u[v.size() / 2]], v[u[v.size() / 2 - 1]]);
return (v[u[v.size() / 2]] + v[u[v.size() / 2 - 1]]) / 2;
}
template <class C, typename U>
inline constexpr std::ptrdiff_t index(const C &v, const U &x) {
return std::distance(v.begin(), find(v, x));
}
template <class C, ENABLE_IF_T(std::is_integral_v<mem_value_type<C>>)>
inline constexpr mem_value_type<C> mex(const C &v) {
std::vector<bool> b(v.size() + 1);
for (const auto &a : v) {
if (0 <= a and static_cast<size_t>(a) < b.size()) {
b[a] = true;
}
}
mem_value_type<C> ret = 0; // b の要素数は v より 1 多いので、下のループで必ず見つかる
for (size_t i = 0; i < b.size(); i++) {
if (not b[i]) {
ret = i;
break;
}
}
return ret;
}
template <class C>
inline constexpr mem_difference_type<C> bisect_left(const C &v, const mem_value_type<C> &x) {
return std::distance(v.begin(), lower_bound(v, x));
}
template <class C>
inline constexpr mem_difference_type<C> bisect_right(const C &v, const mem_value_type<C> &x) {
return std::distance(v.begin(), upper_bound(v, x));
}
#line 2 "src/base/io.hpp"
/**
* @file io.hpp
* @brief 空白区切り出力、iostreamのオーバーロード
*/
#include <array>
#line 13 "src/base/io.hpp"
// ネストした型 (pair<vector<int>, int> など) を扱えるように先に宣言しておく
template <typename T1, typename T2, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::pair<T1, T2>& p);
template <typename... Types, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::tuple<Types...>& p);
template <typename T, size_t N, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::array<T, N>& a);
template <typename T, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::vector<T>& v);
template <typename T1, typename T2, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::pair<T1, T2>& p);
template <typename... Types, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::tuple<Types...>& p);
template <typename T, size_t N, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::array<T, N>& a);
template <typename T, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::vector<T>& v);
template <typename T, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::set<T>& s);
namespace tuple_io {
template <typename Tuple, size_t I, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& read_tuple(std::basic_istream<CharT, Traits>& is, Tuple& t) {
is >> std::get<I>(t);
if constexpr (I + 1 < std::tuple_size_v<Tuple>) {
return read_tuple<Tuple, I + 1>(is, t);
}
return is;
}
template <typename Tuple, size_t I, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& write_tuple(std::basic_ostream<CharT, Traits>& os, const Tuple& t) {
os << std::get<I>(t);
if constexpr (I + 1 < std::tuple_size_v<Tuple>) {
os << CharT(' ');
return write_tuple<Tuple, I + 1>(os, t);
}
return os;
}
};
template <typename T1, typename T2, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::pair<T1, T2>& p) {
is >> p.first >> p.second;
return is;
}
template <typename... Types, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::tuple<Types...>& p) {
return tuple_io::read_tuple<std::tuple<Types...>, 0>(is, p);
}
template <typename T, size_t N, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::array<T, N>& a) {
for(auto& e : a) is >> e;
return is;
}
template <typename T, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::vector<T>& v) {
for(auto& e : v) is >> e;
return is;
}
template <typename T1, typename T2, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::pair<T1, T2>& p) {
os << p.first << CharT(' ') << p.second;
return os;
}
template <typename... Types, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::tuple<Types...>& p) {
return tuple_io::write_tuple<std::tuple<Types...>, 0>(os, p);
}
template <typename T, size_t N, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::array<T, N>& a) {
for(size_t i = 0; i < N; ++i) {
if(i) os << CharT(' ');
os << a[i];
}
return os;
}
template <typename T, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::vector<T>& v) {
for(size_t i = 0; i < v.size(); ++i) {
if(i) os << CharT(' ');
os << v[i];
}
return os;
}
template <typename T, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::set<T>& s) {
for(auto itr = s.begin(); itr != s.end(); ++itr) {
if(itr != s.begin()) os << CharT(' ');
os << *itr;
}
return os;
}
/**
* @brief 空行出力
*/
inline void print() { std::cout << '\n'; }
/**
* @brief 出力して改行
*
* @tparam T 型
* @param x 出力する値
*/
template <typename T>
void print(const T& x) { std::cout << x << '\n'; }
/**
* @brief 空白区切りで出力して改行
*
* @tparam T 1つ目の要素の型
* @tparam Tail 2つ目以降の要素の型
* @param x 1つ目の要素
* @param tail 2つ目以降の要素
*/
template <typename T, typename... Tail>
void print(const T& x, const Tail&... tail) {
std::cout << x << ' ';
print(tail...);
}
/**
* @brief 標準エラー出力に空行出力
*/
inline void err() { std::cerr << std::endl; }
/**
* @brief 標準エラー出力に出力して改行
*
* @tparam T 型
* @param x 出力する値
*/
template <typename T>
void err(const T& x) { std::cerr << x << std::endl; }
/**
* @brief 標準エラー出力に空白区切りで出力して改行
*
* @tparam T 1つ目の要素の型
* @tparam Tail 2つ目以降の要素の型
* @param x 1つ目の要素
* @param tail 2つ目以降の要素
*/
template <typename T, typename... Tail>
void err(const T& x, const Tail&... tail) {
std::cerr << x << ' ';
err(tail...);
}
#line 10 "test/aoj/itp2-5-b.test.cpp"
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
// 価値、重さ、型、日時、名前 (この順の辞書式順序が問題の優先順位と同じ)
std::vector<std::tuple<long long, long long, char, long long, std::string>> items(n);
std::cin >> items; // tuple の vector をまとめて読む
sort(items);
for (const auto& t : items) std::cout << t << '\n'; // tuple を空白区切りで出力
}