fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n';
  4. #define all(x) (x).begin(), (x).end()
  5. #define int long long
  6.  
  7. const int MAXN = 3 * (int)1e6 + 5;
  8.  
  9. int a[MAXN];
  10. vector<int> last(64);
  11.  
  12. void solve() {
  13.   int n, x;
  14.   cin >> n >> x;
  15.   int ans = -1;
  16.  
  17.   int g = 0;
  18.   for (int i = 0; i < n; i++) {
  19.     cin >> a[i];
  20.     g |= a[i];
  21.     if (a[i] >= x) {
  22.       ans = 1;
  23.     }
  24.   }
  25.   if (ans == 1) {
  26.     cout << ans << endl;
  27.     return;
  28.   }
  29.   if (g < x) {
  30.     cout << -1 << endl;
  31.     return;
  32.   }
  33.  
  34.   fill(all(last), -1);
  35.  
  36.   ans = INT_MAX;
  37.  
  38.   int msb = 63 - __builtin_clzll(x);
  39.  
  40.   for (int r = 0; r < n; ++r) {
  41.     for (int b = 0; b <= msb; b++) {
  42.       if (a[r] & (1ll << b)) {
  43.         last[b] = r;
  44.       }
  45.     }
  46.  
  47.     int earliest = 1e18;
  48.     int ok = true;
  49.  
  50.     for (int b = msb; b >= 0; b--) {
  51.       if (x & (1ll << b)) {
  52.         if (last[b] == -1) {
  53.           ok = false;
  54.           break;
  55.         }
  56.         earliest = min(earliest, last[b]);
  57.       } else {
  58.         if (last[b] != -1) {
  59.           ans = min(ans, r - min(earliest, last[b]) + 1);
  60.         }
  61.       }
  62.     }
  63.  
  64.     if (ok) {
  65.       ans = min(ans, r - earliest + 1);
  66.     }
  67.   }
  68.   cout << ans << endl;
  69.   return;
  70. }
  71.  
  72. int32_t main() {
  73.   ios::sync_with_stdio(0);
  74.   cin.tie(0);
  75.  
  76.   int TET = 1;
  77.   cin >> TET;
  78.  
  79.   while (TET--) {
  80.     solve();
  81.   }
  82. }
  83.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
1
11 15
3 2 1 1 2 3 4 4 4 4 8
stdout
copy 
6
https://ideone.com/vWMiDp
language:
C++14 (clang 8.0)
created:
3 days 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!