結果
問題 | No.8090 Knapsack Function |
ユーザー |
|
提出日時 | 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 |
ソースコード
// template {{{#include <bits/stdc++.h>#if __has_include(<debug.hpp>)# include <debug.hpp>#else# define dbg(...) static_cast<void>(0)#endifusing 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_IMPLtemplate<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)));}