fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <bitset>
  3. using namespace std;
  4. #define int long long
  5. #define dd double
  6. #define ld long double
  7. #define ull unsigned long long
  8. #define yes cout << "YES\n"
  9. #define no cout << "NO\n"
  10. #define el "\n"
  11. #define Arwa ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  12. #define fix(x) cout << fixed << setprecision(x)
  13. #define all(v) v.begin(),v.end()
  14. #define dpp(arr,val) memset(arr,val,sizeof(arr))
  15. #define mod 1e9+7
  16. const int N = 1e5 + 5;
  17. int numberOfBits(int n) {
  18.     int cnt = 0;
  19.     while (n > 0) {
  20.         cnt++;
  21.         n >>= 1; // نقسم على 2 باستخدام الـ bit shift
  22.     }
  23.     return cnt;
  24. }
  25. //  First power of two ≥ n
  26. int powerOf2GreaterThanOrEqual(int n)
  27. {
  28.     int indx = 0;
  29.     while ((1 << indx) < n)
  30.         indx++;
  31.     return (1 << indx);
  32. }
  33. int getBit(int n, int indx)
  34. {
  35.     return (n >> indx) & 1;
  36. }
  37. int setBit0(int n, int indx)
  38. {
  39.     return n & ~(1 << indx);
  40. }
  41. bool isPowerOf2(int n)
  42. {
  43.     return n > 0 && (n & (n - 1)) == 0;
  44. }
  45.  
  46. //todo اى ويل بريبير ماى بيبرز تو بى ذا بيست ان زيس وورلد
  47. void HereWeGoAgain()
  48. {
  49.     int n;
  50.     cin>>n;
  51.     int arr[n];
  52.     map<int,int>mp;
  53.     for(int i=0;i<n;i++) cin>>arr[i];
  54.     int mx=arr[0];
  55.     for(int i=1;i<n;i++) mx|=arr[i];
  56.     int orr,k;
  57.     int mxx=numberOfBits(mx);
  58.     for(int i=0;i<n;i++)
  59.     {
  60.         if(arr[i]!=0)
  61.         {
  62.              k=i;
  63.             for(int j=0;j<=mxx;j++)
  64.             {
  65.                 if(!mp[j]&&getBit(arr[i],j))
  66.                 mp[j]=getBit(arr[i],j);
  67.             }
  68.             orr=arr[i];
  69.             break;
  70.         }
  71.     }
  72.     int l=k,minlen=n;
  73.     int count=0;
  74.     //cout<<k<<' '<<orr<<' '<<mx<<el;
  75.     for(int i=k+1;i<n;i++)
  76.     {
  77.         orr|=arr[i];
  78.         for(int j=0;j<=mxx;j++)
  79.         {
  80.         mp[j]+=getBit(arr[i],j);
  81.         if(mp[j]>1) count++;
  82.         }
  83.  
  84.         for(int j=0;j<=mxx;j++)
  85.         {
  86.            int c=l;
  87.            while(mp[j]>1)
  88.            {
  89.                if(getBit(arr[c],j))
  90.                {
  91.                mp[j]--;
  92.                arr[c]=setBit0(arr[c],j);
  93.                }
  94.                c++;
  95.            }
  96.         } 
  97.         //for(auto it:arr) cout<<it<<' ';
  98.         //cout<<el;
  99.         while(arr[l]==0) l++; 
  100.         if(orr==mx) 
  101.         {
  102.        // cout<<l<<' '<<i<<el;
  103.         minlen=min(i-l+1,minlen);
  104.         }
  105.  
  106.     }
  107.    cout<<minlen;
  108. }
  109. int32_t main() 
  110. {
  111.  
  112.     Arwa
  113.     int t=1;
  114.     //cin>>t;
  115.     for(int i=1;i<=t;i++)
  116.     {
  117.     HereWeGoAgain();
  118.     }
  119.     return 0;
  120. }
  121.  
  122.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/l9AE2Q
language:
C++ (gcc 8.3)
created:
9 hours 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!