ugipro_lib_cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub CURRY-AND-RICE/ugipro_lib_cpp

:heavy_check_mark: tests/bit/bit_exhaustive_search.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A"


#include <bits/stdc++.h>
#include "ugilib/base/constants.hpp"
#include "ugilib/base/definitions.hpp"
#include "ugilib/bit/bit_exhaustive_search.hpp"

using namespace std;

// speed up
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// reader
struct rd {
    static ll i() {ll i; cin >> i; return i;}  // long long
    static ld d() {ld d; cin >> d; return d;}  // long double
    static string s() {string s; cin >> s; return s;}  // string
    static char c() {char c; cin >> c; return c;}  // char
    static vector<ll> vi(int n) {vector<ll> v(n); rep(i, n) cin >> v[i]; return v;}  // vector<long long>
    static vector<pair<ll, ll>> g(int n) {vector<pair<ll, ll>> v(n); rep(i, n) cin >> v[i].first >> v[i].second; return v;}  // vector<pair<long long, long long>>
    // tuple
    template<typename... Args> static tuple<Args...> t() {
        tuple<Args...> values;
        apply([](auto&... args) { ((cin >> args), ...); }, values);
        return values;
    }
};

// debug print utility
namespace deb {
    #include <cxxabi.h>
    // demangle type name
    string demangle(const char* name) {
        int status = -4;
        unique_ptr<char, void(*)(void*)> res{
            abi::__cxa_demangle(name, NULL, NULL, &status),
            free
        };
        return (status == 0) ? string(res.get()) : name ;
    }
    // meta functions for type traits
    template<typename T>
    constexpr bool isArithmeticContainer() { return is_arithmetic<typename T::value_type>::value; }
    // for SFINAE
    template<typename T, typename = void> struct has_key_and_mapped_type : false_type {};
    template<typename T> struct has_key_and_mapped_type<T, void_t<typename T::key_type, typename T::mapped_type>> : true_type {};
    // for map or unordered_map
    template<typename T>
    constexpr bool isMapLike() { return has_key_and_mapped_type<T>::value; }

    // for values
    template<typename T, typename enable_if<is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& x) { cout << x << " "; }
    // for pairs
    template <typename T, typename S>
    void p(const pair<T, S>& _p){ p(_p.first); p(_p.second); cout << endl; }
    // for containers
    template<typename T,  typename enable_if<!is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& container) {
        // map and unordered_map
        if constexpr (isMapLike<T>()) {
            cout << demangle(typeid(T).name()) << ":" << endl;
            for (const auto& kv : container) {
                cout << "[" << kv.first << "] => ";
                p(kv.second);
                if constexpr (is_arithmetic_v<typename T::mapped_type>) cout << endl;
            }
        // vector or set or others
        } else {
            if constexpr (!isArithmeticContainer<T>()) cout << demangle(typeid(T).name()) << ":" << endl;
            for (auto it = begin(container); it != end(container); ++it) {
                p(*it);
            }
            if constexpr (isArithmeticContainer<T>()) cout << endl;
        }
    }
};  // namespace deb

int main() {
    // speed up io
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    // code
    ll n = rd::i();
    auto a = rd::vi(n);
    ll q = rd::i();
    auto m = rd::vi(q);

    unordered_set<ll> numbers;
    auto f = [&](const auto &&bits) {
        ll sum = 0;
        for (int i = 0; i < n; i++) {
            if (bits[i]) sum += a[i];
        }
        numbers.insert(sum);
        return false;
    };
    ugilib::bit_exhaustive_search(n, f);

    rep(i, q) {
        if (numbers.find(m[i]) != numbers.end()) cout << "yes" << endl;
        else cout << "no" << endl;
    }

    return 0;
}
#line 1 "tests/bit/bit_exhaustive_search.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A"


#include <bits/stdc++.h>
#line 2 "ugilib/base/definitions.hpp"

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i, n) for(size_t i = 0; i < n; i++)  // rep macro
#define all(v) begin(v), end(v)  // all iterator
#line 3 "ugilib/base/constants.hpp"

namespace ugilib::constants {
    template<typename T>
    inline constexpr T INF = std::numeric_limits<T>::max() / 2;
} // namespace ugilib::constants

const ll INF = ugilib::constants::INF<ll>;
#line 4 "ugilib/bit/bit_util.hpp"

using namespace std;

namespace ugilib {
    /**
     * @brief 数値 -> ビット配列
     * @param num ビット配列にするための数値
     * @param digit ビット数
     * @return vector<bool> 変換されたビット配列. 0番目が一番下の桁
     * @details 数値を指定桁のビット配列に変換する
    */
    vector<bool> num_to_bits(const ll num, const size_t &digit) {
        vector<bool> bits(digit);
        for (int i = 0; i < digit; i++) {
            bits[i] = (num >> i) & 1U;
        }
        return bits;
    }

    /**
     * @brief ビット配列 -> 数値
     * @param bits 数値にするためのビット配列. 0番目が一番下の桁
     * @return ll 変換された数値
     * @details ビット配列を数値に戻す. num_to_bitsの逆変換
    */
    ll bits_to_num(const vector<bool> &bits) {
        ll num = 0;
        for (int i = 0; i < bits.size(); i++) {
            num += bits[i] << i;
        }
        return num;
    }
}  // namespace ugilib
#line 4 "ugilib/bit/bit_exhaustive_search.hpp"

namespace ugilib {
    /**
     * @brief ビット全探索
     * @param digit ビット数
     * @param f ビット配列を渡して、それに応じた処理を行う関数
     * @details ラムダを受け取って、ビット全探索を行う
     * @example
     * vector<int> ans;
     * auto f = [&](const auto &&bits) {
     *    if (count(bits.begin(), bits.end(), true) == 2) {
     *        ans.push_back(bits_to_num(bits));
     *    }
     *    return false;
     * };
     * bit_exhaustive_search(4, f);
     * // ans = {3, 5, 6, 9, 10, 12}
     *
    */
    template <typename Func>
    void bit_exhaustive_search(const size_t &digit, Func f) {
        for (ll i = 0; i < (1 << digit); i++) {
            bool will_break = f(num_to_bits(i, digit));
            if (will_break) break;
        }
    }
}  // namespace ugilib
#line 8 "tests/bit/bit_exhaustive_search.test.cpp"

using namespace std;

// speed up
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// reader
struct rd {
    static ll i() {ll i; cin >> i; return i;}  // long long
    static ld d() {ld d; cin >> d; return d;}  // long double
    static string s() {string s; cin >> s; return s;}  // string
    static char c() {char c; cin >> c; return c;}  // char
    static vector<ll> vi(int n) {vector<ll> v(n); rep(i, n) cin >> v[i]; return v;}  // vector<long long>
    static vector<pair<ll, ll>> g(int n) {vector<pair<ll, ll>> v(n); rep(i, n) cin >> v[i].first >> v[i].second; return v;}  // vector<pair<long long, long long>>
    // tuple
    template<typename... Args> static tuple<Args...> t() {
        tuple<Args...> values;
        apply([](auto&... args) { ((cin >> args), ...); }, values);
        return values;
    }
};

// debug print utility
namespace deb {
    #include <cxxabi.h>
    // demangle type name
    string demangle(const char* name) {
        int status = -4;
        unique_ptr<char, void(*)(void*)> res{
            abi::__cxa_demangle(name, NULL, NULL, &status),
            free
        };
        return (status == 0) ? string(res.get()) : name ;
    }
    // meta functions for type traits
    template<typename T>
    constexpr bool isArithmeticContainer() { return is_arithmetic<typename T::value_type>::value; }
    // for SFINAE
    template<typename T, typename = void> struct has_key_and_mapped_type : false_type {};
    template<typename T> struct has_key_and_mapped_type<T, void_t<typename T::key_type, typename T::mapped_type>> : true_type {};
    // for map or unordered_map
    template<typename T>
    constexpr bool isMapLike() { return has_key_and_mapped_type<T>::value; }

    // for values
    template<typename T, typename enable_if<is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& x) { cout << x << " "; }
    // for pairs
    template <typename T, typename S>
    void p(const pair<T, S>& _p){ p(_p.first); p(_p.second); cout << endl; }
    // for containers
    template<typename T,  typename enable_if<!is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& container) {
        // map and unordered_map
        if constexpr (isMapLike<T>()) {
            cout << demangle(typeid(T).name()) << ":" << endl;
            for (const auto& kv : container) {
                cout << "[" << kv.first << "] => ";
                p(kv.second);
                if constexpr (is_arithmetic_v<typename T::mapped_type>) cout << endl;
            }
        // vector or set or others
        } else {
            if constexpr (!isArithmeticContainer<T>()) cout << demangle(typeid(T).name()) << ":" << endl;
            for (auto it = begin(container); it != end(container); ++it) {
                p(*it);
            }
            if constexpr (isArithmeticContainer<T>()) cout << endl;
        }
    }
};  // namespace deb

int main() {
    // speed up io
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    // code
    ll n = rd::i();
    auto a = rd::vi(n);
    ll q = rd::i();
    auto m = rd::vi(q);

    unordered_set<ll> numbers;
    auto f = [&](const auto &&bits) {
        ll sum = 0;
        for (int i = 0; i < n; i++) {
            if (bits[i]) sum += a[i];
        }
        numbers.insert(sum);
        return false;
    };
    ugilib::bit_exhaustive_search(n, f);

    rep(i, q) {
        if (numbers.find(m[i]) != numbers.end()) cout << "yes" << endl;
        else cout << "no" << endl;
    }

    return 0;
}
Back to top page