fork download
copy 
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <list>
  9. #include <time.h>
  10. #include <math.h>
  11. #include <random>
  12. #include <deque>
  13. #include <queue>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include <iomanip>
  18. #include <bitset>
  19. #include <sstream>
  20. #include <chrono>
  21. #include <cstring>
  22.  
  23. using namespace std;
  24.  
  25. typedef unsigned long long ll;
  26.  
  27. #ifdef iq
  28.   mt19937 rnd(228);
  29. #else
  30.   mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  31. #endif
  32.  
  33. const int N = 1e5;
  34.  
  35. bitset <N> a, b;
  36.  
  37. int main() {
  38. #ifdef iq
  39.   freopen("a.in", "r", stdin);
  40. #endif
  41.   ios::sync_with_stdio(0);
  42.   cin.tie(0);
  43.   int t;
  44.   cin >> t;
  45.   while (t--) {
  46.     string l, r;
  47.     cin >> l >> r;
  48.     reverse(l.begin(), l.end());
  49.     reverse(r.begin(), r.end());
  50.     a.reset(), b.reset();
  51.     int mx = max(l.size(), r.size()) + 1;
  52.     vector <ll> a(mx / 64 + 1);
  53.     vector <ll> b(mx / 64 + 1);
  54.     ll one = 1ll;
  55.     for (int i = 0; i < (int) l.size(); i++) {
  56.       if (l[i] == '1') {
  57.         a[i / 64] += (one << (i % 64));
  58.       }
  59.     }
  60.     for (int i = 0; i<  (int) r.size(); i++) {
  61.       if (r[i] == '1') {
  62.         b[i / 64] += (one << (i % 64));
  63.       }
  64.     }
  65.     int its = 0;
  66.     while (true) {
  67.       bool bad = false;
  68.       for (int i = 0; i < b.size(); i++) if (b[i]) bad = true;
  69.       if (!bad) break;
  70.       auto u = a, v = a;
  71.       for (int i = 0; i < b.size(); i++) {
  72.         u[i] ^= b[i], v[i] &= b[i];
  73.       }
  74.       int was = 0;
  75.       for (int i = 0; i < b.size(); i++) {
  76.         int mem = ((v[i] >> 63) & 1);
  77.         ll go = v[i] & ((one << 63) - 1);
  78.         go <<= 1;
  79.         if (was) go ^= 1;
  80.         was = mem;
  81.         v[i] = go;
  82.       }
  83.       a = u, b = v;
  84.       its++;
  85.     }
  86.     /*
  87.     reverse(a.begin(), a.end());
  88.     reverse(b.begin(), b.end());
  89.     int init = a.size();
  90.     int mx = max((int) a.size(), (int) b.size());
  91.     while (a.size() < mx) a += '0';
  92.     while (b.size() < mx) b += '0';
  93.     int um = 0;
  94.     int tot = 0;
  95.     for (int i = 0; i < (int) a.size(); i++) {
  96.       int cur = (a[i] - '0' + b[i] - '0' + um);
  97.       if (i <= init && (b[i] - '0' + um) > 0) tot++;
  98.       um = cur / 2;
  99.     }
  100.     cout << tot << '\n';
  101.     */
  102.     cout << its << '\n';
  103.   }
  104. }
Success #stdin #stdout 0s 4368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tyJHCd
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!