fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using i64 = int64_t; using u32 = uint32_t;
  4. using u64 = uint64_t; using u128 = __uint128_t;
  5. using ll = long long; using lld = long double; using ull = unsigned long long; 
  6.  
  7. #define rep(i, n) for (int i = 0; i < (n); i++)
  8. #define el '\n'
  9. #define nl cout << "\n"
  10. #define ws " "
  11. #define yes cout << "YES\n"
  12. #define no cout << "NO\n"
  13. #define nai cout << "-1\n"
  14. #define pbk push_back
  15. #define mkp make_pair
  16. #define ff first
  17. #define ss second
  18. #define pii pair<int, int>
  19. #define pll pair<ll, ll>
  20. #define all(v) v.begin(), v.end()
  21. #define rall(v) v.rbegin(), v.rend()
  22. #define vec vector
  23. #define vi vector<int>
  24. #define vl vector<ll>
  25. #define popcnt(x) __builtin_popcountll(x)
  26.  
  27. #ifdef LOCAL
  28. #include "cf_template.cpp"
  29. #else
  30. #define debug(...)
  31. #define debugArr(...)
  32. #endif
  33.  
  34. template<typename T> void print(const T& a) { cout << a << "\n"; }
  35. template<typename T> void print(const vector<T>& v)
  36. { for (auto& x : v) cout << x << " "; cout << "\n"; }
  37. template<typename T, typename... Args>
  38. void print(const T& first, const Args&... rest)
  39. { cout << first; ((cout << ' ' << rest), ...); cout << '\n'; }
  40.  
  41. static inline int msb_index(ull x) {
  42.     return 63 - __builtin_clzll(x);
  43. }
  44.  
  45. void sed() {
  46.     int n; cin >> n; 
  47.  
  48.     vi dp(61), msb[61]; 
  49.     vl arr(n);
  50.     rep(i, n) {
  51.         cin >> arr[i]; 
  52.         if (!arr[i]) continue;
  53.  
  54.         int m = msb_index(arr[i]); 
  55.         msb[m].pbk(i);  dp[m] = 1; 
  56.     }
  57.  
  58.     for (int i = 1; i < 61; i++) {
  59.         for (auto ind : msb[i]) {
  60.             for (int j = i - 1; j >= 0; j--) {
  61.                 if (!(arr[ind] & (1ll << j))) continue;
  62.                 dp[i] = max(dp[i], 1 + dp[j]); 
  63.             }
  64.         }
  65.     }
  66.  
  67.     int ans = *max_element(all(dp)); 
  68.     print(max(1, ans)); 
  69. }   
  70.  
  71. int32_t main(void) {
  72.     ios::sync_with_stdio(false); cin.tie(nullptr);
  73.     int t = 1;
  74.     cin >> t;
  75.     for (int i = 1; i <= t; i++)
  76.         sed();
  77. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/cIl7b1
language:
C++ (gcc 8.3)
created:
57 days 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!