fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5.  
  6. using namespace std;
  7. using namespace __gnu_pbds;
  8.  
  9. #define El_Hefnawys                   \
  10.     ios_base::sync_with_stdio(false); \
  11.     cin.tie(nullptr);                 \
  12.     cout.tie(nullptr)
  13.  
  14. typedef long long ll;
  15. typedef unsigned long long ull;
  16.  
  17.  
  18. typedef vector<vector<ll> > GRAPH;
  19.  
  20. const ll MOD = 1e9 + 7;
  21. const ll OO = 1e18;
  22. const double PI = acos(-1.0);
  23.  
  24. ll dx4[4] = {0, 1, 0, -1};
  25. ll dy4[4] = {1, 0, -1, 0};
  26.  
  27. ll dx8[8] = {0, 0, 1, -1, 1, 1, -1, -1};
  28. ll dy8[8] = {1, -1, 0, 0, 1, -1, 1, -1};
  29.  
  30. ll n, m;
  31. ll dp[1 << 15];
  32. map<ll, ll> mp;
  33.  
  34. ll sol(ll mask, ll cnt) {
  35.     if (cnt > 50000)
  36.         return OO;
  37.     if (mask == 0)
  38.         return 0;
  39.     auto& ret = dp[mask];
  40.     if (~ret)
  41.         return ret;
  42.     ret = OO;
  43.     for (ll i = 0; i < m; i++)
  44.         ret = min(ret, 1 + sol(mask ^ mp[i], cnt + 1));
  45.     return ret;
  46. }
  47.  
  48. void solve(int i) {
  49.     mp.clear();
  50.     cin >> n >> m;
  51.     for (ll i = 0; i < m; i++) {
  52.         string s;
  53.         for (int j = 0; j < n; j++) {
  54.             int x;
  55.             cin >> x;
  56.             s += ('0' + x);
  57.             mp[i] = stoll(s, 0, 2);
  58.         }
  59.     }
  60.     memset(dp, -1, sizeof dp);
  61.     cout << "Case " << i << ": ";
  62.     ll ans = sol((1 << n) - 1, 0);
  63.     if (ans >= OO)
  64.         cout << "IMPOSSIBLE\n";
  65.     else
  66.         cout << ans << "\n";
  67. }
  68.  
  69. signed main() {
  70.     El_Hefnawys;
  71.     // freopen("input.in", "r", stdin);
  72.     // freopen("output.out", "w", stdout);
  73.     ll t{1};
  74.     cin >> t;
  75.     for (int i = 1; i <= t; i++) {
  76.         solve(i);
  77.     }
  78.     return 0;
  79. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1: 0
https://ideone.com/FSClu9
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!