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. //  First power of two ≥ n
  18. int powerOf2GreaterThanOrEqual(int n)
  19. {
  20.     int indx = 0;
  21.     while ((1 << indx) < n)
  22.         indx++;
  23.     return (1 << indx);
  24. }
  25. int getBit(int n, int indx)
  26. {
  27.     return (n >> indx) & 1;
  28. }
  29. int setBit0(int n, int indx)
  30. {
  31.     return n & ~(1 << indx);
  32. }
  33. //todo اى ويل بريبير ماى بيبرز تو بى ذا بيست ان زيس وورلد
  34. void HereWeGoAgain()
  35. {
  36.     int n;
  37.     cin>>n;
  38.     int arr[n];
  39.     map<int,int>mp;
  40.     for(int i=0;i<n;i++) cin>>arr[i];
  41.     int mx=arr[0];
  42.     for(int i=1;i<n;i++) mx|=arr[i];
  43.     int orr,k;
  44.     for(int i=0;i<n;i++)
  45.     {
  46.         if(arr[i]!=0)
  47.         {
  48.              k=i;
  49.             for(int j=0;j<=31;j++)
  50.             {
  51.                 if(!mp[j]&&getBit(arr[i],j))
  52.                 mp[j]+=getBit(arr[i],j);
  53.             }
  54.             orr=arr[i];
  55.             break;
  56.         }
  57.     }
  58.     int l=k,minlen=n;
  59.     //cout<<k<<' '<<orr<<' '<<mx<<el;
  60.     for(int i=k+1;i<n;i++)
  61.     {
  62.         orr|=arr[i];
  63.         int count=0; bool f=0;
  64.         for(int j=0;j<=31;j++)
  65.         {
  66.         if(!mp[j]&&getBit(arr[i],j))
  67.         {
  68.         mp[j]+=getBit(arr[i],j);
  69.         }
  70.         else 
  71.         if(mp[j]&&getBit(arr[i],j))
  72.         {
  73.         mp[j]+=getBit(arr[i],j);
  74.         count++;
  75.         }
  76.         }
  77.             for(int j=0;j<=31;j++)
  78.             {
  79.                 while(mp[j]>1)
  80.                 {
  81.                 if(getBit(arr[l],j))
  82.                 {
  83.                 mp[j]--; arr[l]=setBit0(arr[l],j);
  84.                 while(arr[l]==0) l++;
  85.                 }
  86.                 else l++;
  87.                 }
  88.             }
  89.         if(orr==mx) 
  90.         {
  91.         //cout<<l<<' '<<i<<el;
  92.         minlen=min(i-l+1,minlen);
  93.         }
  94.  
  95.     }
  96.    // 0 1 2 3 
  97.    cout<<minlen;
  98. }
  99. int32_t main() 
  100. {
  101.  
  102.     Arwa
  103.     int t=1;
  104.     //cin>>t;
  105.     for(int i=1;i<=t;i++)
  106.     {
  107.     HereWeGoAgain();
  108.     }
  109.     return 0;
  110. }
  111.  
  112.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0B2t1u
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!