fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main() {
  6.   ios::sync_with_stdio(false);
  7.   cin.tie(nullptr);
  8.  
  9.   int T;
  10.   cin >> T;
  11.   while (T--) {
  12.     int n;
  13.     ll x;
  14.     cin >> n >> x;
  15.     vector<ll> a(n);
  16.     for (int i = 0; i < n; i++)
  17.       cin >> a[i];
  18.  
  19.     // cnt[k] = how many elements in [l..r] have bit k set
  20.     int cnt[64] = {};
  21.     ll curr_or = 0;
  22.     int ans = INT_MAX;
  23.     int l = 0;
  24.  
  25.     for (int r = 0; r < n; r++) {
  26.       // add a[r]
  27.       ll v = a[r];
  28.       while (v) {
  29.         int b = __builtin_ctzll(v);
  30.         if (cnt[b]++ == 0)
  31.           curr_or |= (1LL << b);
  32.         v &= v - 1;
  33.       }
  34.       // try to shrink from left
  35.       while (l <= r && curr_or >= x) {
  36.         ans = min(ans, r - l + 1);
  37.         // remove a[l]
  38.         ll w = a[l++];
  39.         while (w) {
  40.           int b = __builtin_ctzll(w);
  41.           if (--cnt[b] == 0)
  42.             curr_or &= ~(1LL << b);
  43.           w &= w - 1;
  44.         }
  45.       }
  46.     }
  47.  
  48.     cout << (ans == INT_MAX ? -1 : ans) << "\n";
  49.   }
  50.   return 0;
  51. }
  52.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
1
11 15
3 2 1 1 2 3 4 4 4 4 8
stdout
copy 
6
https://ideone.com/nv7zRF
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!