fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/rope>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. //#pragma GCC optimize("Ofast")
  6. //#pragma GCC optimize("unroll-loops")
  7. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  8. //#define int long long
  9. #define pb push_back
  10. #define x first
  11. #define y second
  12. #define mk(a,b) make_pair(a,b)
  13. #define rr return 0
  14. #define sqr(a) ((a)*(a))
  15. #define all(a) (a).begin(), (a).end()
  16. #define sz(a) (int)(a).size()
  17. #define name(a) #a
  18.  
  19. using namespace std;
  20. using namespace __gnu_cxx;
  21. using namespace __gnu_pbds;
  22.  
  23. using ll = long long;
  24. using ld = long double;
  25. using pii = pair<int, int>;
  26. using pll = pair<ll, ll>;
  27.  
  28. template<class value, class cmp = less<value> >
  29. using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  30. template<class value, class cmp = less_equal<value> >
  31. using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  32. template<class key, class value, class cmp = less<key> >
  33. using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  34.  
  35. /// find_by_order()
  36. /// order_of_key()
  37. mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
  38. inline int randll(int l = INT_MIN, int r = INT_MAX) {
  39.     return uniform_int_distribution<int>(l, r)(rng);
  40. }
  41.  
  42. const int INF = 1e9, MOD = 1e9 + 7; /// think
  43. const ll LINF = 1e18;
  44.  
  45. const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
  46. inline bool inside (int x, int y, int n, int m) {
  47.     return 0 <= x && 0 <= y && x < n && y < m;
  48. }
  49.  
  50. template<class T> bool umin (T &a, T b) {return a > b ? (a = b, true) : false; }
  51. template<class T> bool umax (T &a, T b) {return a < b ? (a = b, true) : false; }
  52.  
  53. const int M = 20;
  54. const int N = 1 << M;
  55.  
  56.  
  57.  
  58. bitset<N> used;
  59. inline void dfs (int v, vector <int> &a, vector <int> &b) {
  60.     used[v] = 1;
  61.     for (int i : a) {
  62.         int to = v | i;
  63.         if (!used[to]) {
  64.             dfs(to, a, b);
  65.         }
  66.     }
  67.     for (int i : b) {
  68.         int to = v & i;
  69.         if (!used[to]) {
  70.             dfs(to, a, b);
  71.         }
  72.     }
  73. }
  74. inline int stupid(int n, int m, vector <int> a, vector <int> b) {
  75.     used.reset();
  76.     dfs(0, a, b);
  77. //    cout << used.count() << '\n';
  78.     return used.count();
  79. }
  80.  
  81.  
  82. inline void solve1 () {
  83.     int n, m;
  84.     cin >> n >> m;
  85.     vector <int> a(n), b(m);
  86.     for (auto &i : a) cin >> i;
  87.     for (auto &i : b) cin >> i;
  88.     sort(all(a));
  89.     sort(all(b));
  90.     reverse(all(b));
  91.  
  92.     vector <int> A;
  93.     vector <int> c(N);
  94.     while (true) {
  95.         bool ok = true;
  96.         for (auto &i : a) {
  97.             if (c[i] != i) {
  98.                 A.pb(i);
  99.                 c[i] |= i;
  100.                 for (int mask = i; mask < N; mask = i | (mask + 1)) {
  101.                     c[mask] |= i;
  102.                 }
  103.                 ok = false;
  104.                 break;
  105.             }
  106.         }
  107.         if (ok) break;
  108.     }
  109.  
  110.     vector <int> B;
  111.     vector <int> d(N, N - 1);
  112.     while (true) {
  113.         bool ok = true;
  114.         for (auto &i : b) {
  115.             if (d[i] != i) {
  116.                 B.pb(i);
  117.                 d[i] &= i;
  118.                 for (int mask = i; mask > 0; mask = i & (mask - 1)) {
  119.                     d[mask] &= i;
  120.                 }
  121.                 ok = false;
  122.                 break;
  123.             }
  124.         }
  125.         if (ok) break;
  126.     }
  127.     int ans = stupid(sz(A), sz(B), A, B);
  128.     cout << ans << '\n';
  129. }
  130.  
  131. main()
  132. {
  133.     ios::sync_with_stdio(0);
  134.     ios_base::sync_with_stdio(0);
  135.     cin.tie(0);
  136.     cout.tie(0);
  137.     int t;
  138.     cin >> t;
  139.     while (t--) {
  140.         solve1();
  141.     }
  142. }
  143.  
Time limit exceeded #stdin #stdout 5s 914224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bkZLow
language:
C++14 (gcc 8.3)
created:
3 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!