API tools faq
paste
mr_dot_convict

844E-Binary-Matrix-codeforces-mr.convict

mr_dot_convict
May 5th, 2020
154
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.63 KB | None | 0 0
raw download clone embed print report
  1. // Hack it and have it ;) //
  2. /*author* Priyanshu Shrivastav (from IIT Palakkad) *
  3.  * *_ __ ___  _ ______ ___  _ ____   ___  ___| |_  *
  4.  * | '_ ` _ \| '__/ __/ _ \| '_ \ \ / / |/ __| __| *
  5.  * | | | | | | | | (_| (_) | | | \ V /| | (__| |_  *
  6.  * |_| |_| |_|_|(_)___\___/|_| |_|\_/ |_|\___|\__| *
  7. When I wrote this, only God and I understood what I was doing
  8.  ** * * * * * * * Now, only God knows!* * * * * * */
  9. #include      <bits/stdc++.h> /*{{{*/
  10. #include      <ext/pb_ds/assoc_container.hpp>
  11. #include      <ext/pb_ds/tree_policy.hpp>
  12. using namespace std;
  13. using namespace __gnu_pbds;
  14.  
  15. #ifdef CONVICTION
  16. #pragma GCC       optimize ("Ofast")
  17. #pragma GCC       optimize ("unroll-loops")
  18. #pragma GCC       target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  19. #endif
  20.  
  21. #define IOS       ios_base::sync_with_stdio(false); cin.tie (nullptr)
  22. #define PREC      cout.precision (10); cout << fixed
  23. #define X         first
  24. #define Y         second
  25. #define sz(x)     (int)x.size()
  26. #define fr(i,x,y) for (int i = (int)x; i <= (int)y; ++i)
  27. #define rv(i,x,y) for (int i = (int)x; i >= (int)y; --i)
  28. #define bcnt(x)   __builtin_popcount(x)
  29. #define bcntll(x) __builtin_popcountll(x)
  30. #define bg(x)     " [ " << #x << " : " << (x) << " ] "
  31. #define un(x)     sort(x.begin(), x.end()), \
  32.   x.erase(unique(x.begin(), x.end()), x.end())
  33. using   ll  =     long long;
  34. using   ull =     unsigned long long;
  35. using   ff  =     long double;
  36. using   pii =     pair<int,int>;
  37. using   pil =     pair<int,ll>;
  38. using   pll =     pair<ll,ll>;
  39. using   vi  =     vector <int>;
  40. using   vl  =     vector<ll>;
  41. using   vvi =     vector <vi>;
  42. using   vvl =     vector <vl>;
  43. using   vp  =     vector <pii>;
  44. using   vvp =     vector <vp>;
  45. typedef tree
  46. < int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  47. ordered_set;
  48.  
  49. struct chash {
  50.   int operator () (pii x) const { return x.X*31 + x.Y; }
  51. };
  52. gp_hash_table <pii, int, chash> gmp;
  53.  
  54. #if __cplusplus > 201103L
  55. seed_seq seq{
  56.   (uint64_t) chrono::duration_cast<chrono::nanoseconds>
  57.     (chrono::high_resolution_clock::now().time_since_epoch()).count(),
  58.     (uint64_t) __builtin_ia32_rdtsc(),
  59.     (uint64_t) (uintptr_t) make_unique<char>().get()
  60. };
  61. mt19937 rng(seq); //uniform_int_distribution<int> (l, h)(rng); //[low, high]
  62. #else
  63. auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  64. mt19937 rng(seed);
  65. #endif
  66.  
  67. #ifdef CONVICTION
  68. void __print(int x) {cerr << x;}
  69. void __print(long x) {cerr << x;}
  70. void __print(long long x) {cerr << x;}
  71. void __print(unsigned x) {cerr << x;}
  72. void __print(unsigned long x) {cerr << x;}
  73. void __print(unsigned long long x) {cerr << x;}
  74. void __print(float x) {cerr << x;}
  75. void __print(double x) {cerr << x;}
  76. void __print(long double x) {cerr << x;}
  77. void __print(char x) {cerr << '\'' << x << '\'';}
  78. void __print(const char *x) {cerr << '\"' << x << '\"';}
  79. void __print(const string &x) {cerr << '\"' << x << '\"';}
  80. void __print(bool x) {cerr << (x ? "true" : "false");}
  81.  
  82. template<typename T, typename V>
  83. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  84. template<typename T>
  85. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  86. void _print() {cerr << "]" << endl;}
  87. template <typename T, typename... V>
  88. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  89. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  90. #else
  91. #define debug(x...)
  92. #endif
  93. //         __                                           __
  94. //        (**)                                         (**)
  95. //        IIII                                         IIII
  96. //        ####                                         ####
  97. //        HHHH     Madness comes, and madness goes     HHHH
  98. //        HHHH    An insane place, with insane moves   HHHH
  99. //        ####   Battles without, for battles within   ####
  100. //     ___IIII___        Where evil lives,          ___IIII___
  101. //  .-`_._"**"_._`-.      and evil rules         .-`_._"**"_._`-.
  102. // |/``  .`\/`.  ``\|    Breaking them up,      |/``  .`\/`.  ``\|
  103. // `     }    {     '  just breaking them in    `     }    {     '
  104. //       ) () (  Quickest way out, quickest way wins  ) () (
  105. //       ( :: )      Never disclose, never betray     ( :: )
  106. //       | :: |   Cease to speak or cease to breath   | :: |
  107. //       | )( |        And when you kill a man,       | )( |
  108. //       | || |          you're a murderer            | || |
  109. //       | || |             Kill many                 | || |
  110. //       | || |        and you're a conqueror         | || |
  111. //       | || |        Kill them all ... Ooh..        | || |
  112. //       | || |           Oh you're a God!            | || |
  113. //       ( () )                       -Megadeth       ( () )
  114. //        \  /                                         \  /
  115. //         \/                                           \/
  116. /*}}}*/
  117. /*****************************************************************************/
  118. //Don’t practice until you get it right. Practice until you can’t get it wrong
  119. //
  120. const int M = (1 << 14) + 10;
  121. int pp[M], pn[M], pi[M + M], mark[M], vis[M + M], rnk[M + M];
  122. int prv[M], nxt[M];
  123. char foo[M];
  124.  
  125. inline int node (int x) {
  126.     int y = x, tmp;
  127.     while (y != pi[y]) y = pi[y];
  128.     while (x != pi[x]) tmp = pi[x], pi[x] = y, x = tmp;
  129.     return y;
  130. };
  131.  
  132. void solve() {
  133.   int n, m;
  134.   scanf("%i%i", &n, &m);
  135.   // cin >> n >> m;
  136.  
  137.   for (int i = 0; i < 2 * m; ++i) pi[i] = i, rnk[i] = 1;
  138.  
  139.   int res = 0;
  140.   for (int i = 0; i < m; ++i) prv[i] = 0;
  141.   for (int rot = 0; rot <= n; ++rot) {
  142.     for (int i = 0; i < m; ++i) nxt[i] = 0;
  143.     if (rot != n) {
  144.       scanf("%s", foo);
  145.       for (int i = 0; i < m/4; ++i) {
  146.         char ch = foo[i];
  147.         int el = (ch - '0' >= 0 && ch - '0' <= 9 ? 0 + (ch - '0') : 10 + (ch - 'A'));
  148.         for (int j = 0; j < 4; ++j)
  149.           if (el & (1 << j)) nxt[i * 4 + 3 - j] = 1;
  150.       }
  151.     }
  152.  
  153.     // set right local pointers
  154.     for (int i = 0; i < m; ++i) pn[i] = -1;
  155.     for (int i = m - 1, rt = m - 1; i >= 0; --i)
  156.       if (nxt[i]) pn[i] = rt;
  157.       else rt = i - 1;
  158.  
  159.     // first : normalize the dsu for the previous string
  160.  
  161.     for (int i = 0; i < m; ++i) mark[i] = -1;
  162.     for (int i = 0; i < m; ++i)  {
  163.       if (prv[i]) {
  164.         int lt = pp[i] + m;
  165.         int nd = node(lt);
  166.         i = pp[i];
  167.         if (nd >= m) continue;
  168.         if (mark[nd] == -1)
  169.           mark[nd] = lt;
  170.         pi[lt] = mark[nd];
  171.       }
  172.     }
  173.     for (int i = 0; i < m; ++i) pi[i] = i;
  174.     for (int i = 0; i < m; ++i)
  175.       if (prv[i])
  176.         pi[i] = pi[i + m] - m;
  177.     for (int i = m; i < m + m; ++i) pi[i] = i;
  178.  
  179.     // second : merge components
  180.  
  181.     for (int i = 0; i < m; ++i) {
  182.       if (nxt[i] && prv[i]) {
  183.         int lt = node(pn[i] + m);
  184.         int nd = node(pp[i]);
  185.         // merge(lt, nd);
  186.         pi[lt] = nd;
  187.       }
  188.     }
  189.  
  190.     // third : update the answer based on left out components (They will never be seen again)
  191.  
  192.     for (int i = 0; i < m + m; ++i) vis[i] = 0;
  193.  
  194.     for (int i = m; i < m + m; ++i) {
  195.       if (nxt[i - m]) {
  196.         int v = node(pn[i - m] + m);
  197.         vis[v] = true;
  198.       }
  199.     }
  200.     for (int i = 0; i < m; ++i) {
  201.       if (prv[i]) {
  202.         int v = node(pp[i]);
  203.         if (!vis[v])
  204.           ++res, vis[v] = true;
  205.       }
  206.     }
  207.     // update and reset
  208.     for (int i = 0; i < m; ++i)
  209.       pp[i] = pn[i], prv[i] = nxt[i];
  210.   }
  211.   printf("%i\n", res);
  212. }
  213.  
  214. signed main() {
  215.   IOS; PREC;
  216.   int tc = 1;
  217.   // cin >> tc;
  218.   for (int Tt = 1; Tt <= tc; ++Tt) {
  219.     // cout << "Case #" << Tt << ": ";
  220.     solve();
  221.   }
  222.   return EXIT_SUCCESS;
  223. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!