結果

問題 No.8090 Knapsack Function
ユーザー atree
提出日時 2022-04-01 22:02:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 22 ms / 2,000 ms
コード長 10,857 bytes
コンパイル時間 1,995 ms
コンパイル使用メモリ 201,356 KB
最終ジャッジ日時 2025-01-28 14:02:14
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// template {{{
#include <bits/stdc++.h>
#if __has_include(<debug.hpp>)
# include <debug.hpp>
#else
# define dbg(...) static_cast<void>(0)
#endif
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using usize = std::size_t;
using bit_t = u64;
constexpr auto operator""_i32(unsigned long long n) noexcept { return static_cast<std::int32_t>(n); }
constexpr auto operator""_i64(unsigned long long n) noexcept { return static_cast<std::int64_t>(n); }
constexpr auto operator""_u32(unsigned long long n) noexcept { return static_cast<std::uint32_t>(n); }
constexpr auto operator""_u64(unsigned long long n) noexcept { return static_cast<std::uint64_t>(n); }
constexpr auto operator""_uz(unsigned long long n) noexcept { return static_cast<size_t>(n); }
constexpr auto operator""_bit(unsigned long long n) noexcept { return static_cast<bit_t>(n); }
template<class T, T N = 2> inline constexpr auto INF = std::numeric_limits<T>::max() / N;
template<class T> constexpr inline std::enable_if_t<std::is_arithmetic_v<T>, T> power(T a, u32 b) {
T ans = 1;
for (; b; b >>= 1) {
if (b & 1) ans *= a;
a *= a;
}
return ans;
}
template<class T> constexpr inline auto TEN(u32 n) { return power(static_cast<T>(10), n); }
constexpr inline auto countr_zero(bit_t n) -> int { return n == 0 ? 64 : __builtin_ctzll(n); }
constexpr inline auto countl_zero(bit_t n) -> int { return n == 0 ? 64 : __builtin_clzll(n); }
constexpr inline auto countr_one(bit_t n) -> int { return n == std::numeric_limits<bit_t>::max() ? 64 : countr_zero(compl n); }
constexpr inline auto countl_one(bit_t n) -> int { return n == std::numeric_limits<bit_t>::max() ? 64 : countl_zero(compl n); }
constexpr inline auto mask(u32 n) -> bit_t { return (static_cast<bit_t>(1) << n) - 1; }
constexpr inline auto popcount(bit_t n) -> int { return __builtin_popcountll(n); }
constexpr inline auto is_pow2(bit_t n) -> bool { return (n & (n - 1)) == 0; }
constexpr inline auto msb(bit_t n) -> int { return 63 - countl_zero(n); }
constexpr inline auto bit_ceil(bit_t n) -> bit_t { return is_pow2(n) ? n : static_cast<bit_t>(1) << msb(n); }
constexpr inline auto bit_floor(bit_t n) -> bit_t { return is_pow2(n) ? n : static_cast<bit_t>(1) << (msb(n) + 1); }
template<class T, class U = T> constexpr auto chmin(T& a, U&& b) -> bool { return b < a ? a = std::forward<U>(b), true : false; }
template<class T, class U = T> constexpr auto chmax(T& a, U&& b) -> bool { return a < b ? a = std::forward<U>(b), true : false; }
template<class> struct is_tuple_like: std::false_type {};
template<class... Ts> struct is_tuple_like<std::tuple<Ts...>>: std::true_type {};
template<class T1, class T2> struct is_tuple_like<std::pair<T1, T2>>: std::true_type {};
template<class T, std::size_t N> struct is_tuple_like<std::array<T, N>>: std::true_type {};
template<class, class = std::void_t<>> struct is_printable: std::false_type {};
template<class T> struct is_printable<T, std::void_t<decltype(std::cout << std::declval<T>())>>: std::true_type {};
template<class, class = std::void_t<>> struct is_iteratable: std::false_type {};
template<class T> struct is_iteratable<T, std::void_t<decltype(std::begin(std::declval<T>()), std::end(std::declval<T>()))>>
: std::true_type {};
template<class, class = std::void_t<>> struct has_val: std::false_type {};
template<class T> struct has_val<T, std::void_t<decltype(std::declval<T>().val())>>: std::true_type {};
template<class T> struct is_1indexed: std::false_type {};
#define INDEXED_IMPL(type) \
struct type##_##1 { \
using base = type; \
}; \
template<> struct is_1indexed<type##_##1>: std::true_type {};
INDEXED_IMPL(int)
INDEXED_IMPL(size_t)
INDEXED_IMPL(i32)
INDEXED_IMPL(u32)
INDEXED_IMPL(i64)
INDEXED_IMPL(u64)
INDEXED_IMPL(usize)
#undef INDEXED_IMPL
template<class F> struct rec_lambda {
F f;
explicit constexpr rec_lambda(F&& f): f(std::forward<F>(f)) {}
template<class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
return f(*this, std::forward<Args>(args)...);
}
};
template<class... Args> auto zip(const std::vector<Args>&... args) {
std::size_t n = std::min({ std::size(args)... });
std::vector<std::tuple<std::decay_t<Args>...>> ret(n);
for (std::size_t i = 0; i < n; ++i) ret[i] = { args[i]... };
return ret;
}
template<class T, size_t N> auto construct_vector(std::vector<size_t>& sizes, T x = std::decay_t<T>{}) {
if constexpr (N == 1) {
return std::vector<std::decay_t<T>>(sizes[0], x);
} else {
size_t size = sizes[N - 1];
sizes.pop_back();
return std::vector(size, construct_vector<T, N - 1>(sizes, x));
}
}
template<class T, size_t N> decltype(auto) make_vector(size_t(&&sizes)[N], T&& x = std::decay_t<T>{}) {
std::vector<size_t> s(N);
for (size_t i = 0; i < N; ++i) s[i] = sizes[N - i - 1];
if constexpr (std::is_invocable_v<std::decay_t<T>>) {
auto ret = construct_vector<std::invoke_result_t<std::decay_t<T>>, N>(s);
rec_lambda([](auto&& self, auto& v, auto&& f) {
for (auto it = std::begin(v); it != std::end(v); ++it) {
if constexpr (std::is_same_v<std::decay_t<decltype(*it)>, std::invoke_result_t<decltype(f)>>) *it = f();
else self(*it, f);
}
})(ret, x);
return ret;
} else {
return construct_vector<std::decay_t<T>, N>(s, x);
}
}
template<class V> auto make_graph(size_t n, const std::vector<std::tuple<V, V>>& edges, bool is_directed = false) {
std::vector graph(n, std::vector<size_t>{});
for (const auto& [u, v]: edges) {
graph[u].emplace_back(v);
if (not is_directed) graph[v].emplace_back(u);
}
return graph;
}
template<class V, class W> auto make_graph(size_t n, const std::vector<std::tuple<V, V, W>>& edges, bool is_directed = false) {
std::vector graph(n, std::vector<std::pair<size_t, W>>{});
for (const auto& [u, v, w]: edges) {
graph[u].emplace_back(v, w);
if (not is_directed) graph[v].emplace_back(u, w);
}
return graph;
}
__attribute__((constructor)) auto io_setup() noexcept {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(10);
std::cerr << std::fixed << std::setprecision(10);
}
// Copyright (c) 2021 Mitama Lab | `tuple_scan`, `scan`, `in` are based on the code released under the ISC license. see
// https://opensource.org/licenses/ISC.
template<class Tp, std::size_t... I> inline decltype(auto) tuple_scan(Tp&, std::index_sequence<I...>);
inline auto scan = [](auto&... args) {
return (..., [&] {
if constexpr (is_tuple_like<std::decay_t<decltype(args)>>::value) {
return tuple_scan(args, std::make_index_sequence<std::tuple_size_v<std::decay_t<decltype(args)>>>{});
} else {
return not (std::cin >> args).fail();
}
}());
};
template<class Tp, std::size_t... I> inline auto tuple_scan(Tp& tup, std::index_sequence<I...>) {
return (... and scan(std::get<I>(tup)));
}
template<class T, class... Args> decltype(auto) inline in();
template<class Tp, std::size_t... I> inline auto tuple_in(std::index_sequence<I...>) {
return std::tuple{ in<typename std::tuple_element_t<I, Tp>>()... };
}
template<class T, class... Args> decltype(auto) inline in() {
if constexpr (sizeof...(Args) == 0) {
if constexpr (is_tuple_like<T>::value) {
auto t = tuple_in<T>(std::make_index_sequence<std::tuple_size_v<T>>());
return t;
} else if constexpr (is_1indexed<T>::value) {
typename T::base x;
scan(x);
--x;
return x;
} else {
T x;
scan(x);
return x;
}
} else {
return std::tuple{ in<T>(), in<Args>()... };
}
}
template<class T, class... size_t> inline auto in_vec(size_t&&... args) {
return make_vector({ static_cast<usize>(args)... }, *in<T>);
}
inline constexpr char sep = ' ';
inline constexpr char eoln = '\n';
inline constexpr auto yes = "Yes";
inline constexpr auto no = "No";
inline auto print(){};
template<class T> inline auto print(T&&) -> void;
template<class Tp, std::size_t... I> inline auto tuple_print(Tp&& tp, std::index_sequence<I...>) -> void {
(
[&] {
print(std::forward<decltype(std::get<I>(tp))>(std::get<I>(tp)));
if constexpr (I + 1 != std::tuple_size_v<std::decay_t<Tp>>) print(sep);
}(),
...);
}
template<class...> constexpr bool false_v = false;
template<class T> inline auto print(T&& x) -> void {
if constexpr (is_printable<std::decay_t<T>>::value) {
if constexpr (std::is_same_v<bool, std::decay_t<T>>) std::cout << (x ? yes : no);
else std::cout << x;
} else if constexpr (is_tuple_like<std::decay_t<T>>::value) {
tuple_print(std::forward<T>(x), std::make_index_sequence<std::tuple_size_v<std::decay_t<T>>>());
} else if constexpr (is_iteratable<T>::value) {
for (auto it = std::begin(x); it != std::end(x); ++it) {
print(std::forward<decltype(*it)>(*it));
if (next(it) != std::end(x)) print(sep);
}
} else if (has_val<std::decay_t<T>>::value) {
print(x.val());
}
}
template<class T, class... Args> inline auto print(T&& t, Args&&... args) {
print(std::forward<T>(t));
print(sep);
print(std::forward<Args>(args)...);
}
template<class... Args> inline auto println(Args&&... args) {
print(std::forward<Args>(args)...);
print(eoln);
}
template<class... Args> [[noreturn]] inline auto drop(Args&&... args) {
println(std::forward<Args>(args)...);
exit(0);
}
#define overload2(_NULL, _1, _2, name, ...) name
#define rep1(i, n) for (std::decay_t<decltype(n)> i = 0; i < (n); i++)
#define rep2(i, a, b) for (std::decay_t<decltype(b)> i = (a); i < (b); i++)
#define rep(...) overload2(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define LAMBDA(...) [&]([[maybe_unused]] const auto& _) { return __VA_ARGS__; }
#define LAMBDA2(...) [&](const auto& _1, const auto& _2) { return __VA_ARGS__; }
// }}}
using namespace std;
auto main() -> int {
const auto n = in<usize>();
const auto items = in_vec<tuple<u32, u32>>(n);
println(any_of(cbegin(items), cend(items), LAMBDA(get<1>(_) == 1)));
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0