fork download
copy 
  1. #include <cmath>
  2. #include <iostream>
  3. #include <map>
  4. #include <vector>
  5. #include <set>
  6. #include <string>
  7. #include <algorithm>
  8. #include <stack>
  9. #include <queue>
  10. #include <cstring>
  11. #include <cstdio>
  12. #include <string>
  13. #include <functional>
  14.  
  15. #define all(cont) cont.begin(), cont.end()
  16. #define rall(cont) cont.end(), cont.begin()
  17. #define tr(cont, it) for (typeof(cont.begin()) it = cont.begin() ; it != cont.end() ; it++)
  18. #define FOR(i, j, k, l) for(int i=(j) ; i<(k) ; i+=(l))
  19. #define rep(i, j) FOR(i, 0, j, 1)
  20. #define rrep(i, j) FOR(i, j, -1, -1)
  21.  
  22. #define INF 1000000000
  23.  
  24. using namespace std;
  25.  
  26. typedef pair<int, int> ii;
  27. typedef vector<int> vi;
  28. typedef vector<ii> vii;
  29. typedef vector<vi> vvi;
  30. typedef long long ll;
  31.  
  32. int T;
  33. ll N, L;
  34. vector<ll> outlets, devices;
  35.  
  36. bool check(const vector<ll>& out2) {
  37.     for (int i=0 ; i<N ; i++) {
  38.         if (out2[i] != devices[i])
  39.             return false;
  40.     }
  41.     return true;
  42. }
  43.  
  44. void pv(vector<ll> v) {
  45.     for (int i=0 ; i<N ; i++) {
  46.         printf("%lld ", v[i]);
  47.     }
  48.     printf("\n");
  49. }
  50.  
  51. int main() {
  52.     scanf("%d", &T);
  53.     for (int t=1 ; t<=T ; t++) {
  54.         scanf("%lld %lld\n", &N, &L);
  55.         outlets.assign(N, 0L);
  56.         devices.assign(N, 0L);
  57.  
  58.         for (ll i=0 ; i<N ; i++) {
  59.             for (ll j=0 ; j<L ; j++) {
  60.                 char temp; scanf("%c", &temp);
  61.                 if (temp == '1') outlets[i] |= (1L << (L - j - 1L));
  62.             }
  63.             scanf(" ");
  64.         }
  65.         scanf("\n");
  66.  
  67.         for (ll i=0 ; i<N ; i++) {
  68.             for (ll j=0 ; j<L ; j++) {
  69.                 char temp; scanf("%c", &temp);
  70.                 if (temp == '1') devices[i] |= (1L << (L - j - 1L));
  71.             }
  72.             scanf(" ");
  73.         }
  74.         scanf("\n");
  75.  
  76.         sort(all(devices));
  77.  
  78.         int ans = 1e9;
  79.         for (ll i=0 ; i<N ; i++) {
  80.             ll flipped = devices[0] ^ outlets[i];
  81.             if (__builtin_popcount(flipped) < ans) {
  82.                 vector<ll> outlets2 = outlets;
  83.                 for (ll k=0 ; k<N ; k++) {
  84.                     outlets2[k] ^= flipped;
  85.                 }
  86.                 sort(all(outlets2));
  87.                 if (check(outlets2)) {
  88.                     ans = __builtin_popcount(flipped);
  89.                 }
  90.             }
  91.         }
  92.  
  93.         printf("Case #%d: ", t);
  94.         if (ans == 1e9) {
  95.             printf("NOT POSSIBLE\n");
  96.         }
  97.         else {
  98.             printf("%d\n", ans);
  99.         }
  100.     }
  101. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
3
3 2
01 11 10
11 00 10
2 3
101 111
010 001
2 2
01 10
10 01
stdout
copy 
Case #1: 1
Case #2: NOT POSSIBLE
Case #3: 0
https://ideone.com/4c47Xe
language:
C++ (gcc 8.3)
created:
11 years 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!