test/aoj/ITP2_11_C/main.desc.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_11_C
• Link: View error logs on GitHub Actions

Depends on

• Enumerate subsets (Descending order) (Mylib/Bit/enumerate_subsets_desc.cpp)
• Input vector (Mylib/IO/input_vector.cpp)

Code

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

#include <iostream>
#include <map>
#include <vector>
#include "Mylib/Bit/enumerate_subsets_desc.cpp"
#include "Mylib/IO/input_vector.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int n, k;
  std::cin >> n >> k;

  int t = 0;
  for (auto b : hl::input_vector<int>(k)) {
    t |= 1 << b;
  }

  std::map<int, std::vector<int>> ans;
  hl::enumerate_subsets_desc(
      t,
      [&](int d) {
        ans[d];
        for (int i = 0; i < n; ++i) {
          if (d & (1 << i)) ans[d].push_back(i);
        }
        return true;
      });

  for (auto& [m, v] : ans) {
    std::cout << m << ":";
    for (auto x : v) std::cout << " " << x;
    std::cout << "\n";
  }

  return 0;
}

#line 1 "test/aoj/ITP2_11_C/main.desc.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_11_C"

#include <iostream>
#include <map>
#include <vector>
#line 2 "Mylib/Bit/enumerate_subsets_desc.cpp"

namespace haar_lib {
  template <typename Func>
  void enumerate_subsets_desc(int a, const Func &f) {
    for (int t = a;; t = (t - 1) & a) {
      if (not f(t)) break;
      if (t == 0) break;
    }
  }
}  // namespace haar_lib
#line 4 "Mylib/IO/input_vector.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<T> input_vector(int N) {
    std::vector<T> ret(N);
    for (int i = 0; i < N; ++i) std::cin >> ret[i];
    return ret;
  }

  template <typename T>
  std::vector<std::vector<T>> input_vector(int N, int M) {
    std::vector<std::vector<T>> ret(N);
    for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
    return ret;
  }
}  // namespace haar_lib
#line 8 "test/aoj/ITP2_11_C/main.desc.test.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int n, k;
  std::cin >> n >> k;

  int t = 0;
  for (auto b : hl::input_vector<int>(k)) {
    t |= 1 << b;
  }

  std::map<int, std::vector<int>> ans;
  hl::enumerate_subsets_desc(
      t,
      [&](int d) {
        ans[d];
        for (int i = 0; i < n; ++i) {
          if (d & (1 << i)) ans[d].push_back(i);
        }
        return true;
      });

  for (auto& [m, v] : ans) {
    std::cout << m << ":";
    for (auto x : v) std::cout << " " << x;
    std::cout << "\n";
  }

  return 0;
}

Back to top page