Advertisement
ekzolot

Untitled

Apr 29th, 2022
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. vector <bool> count_(int n, vector<vector<bool>> bin, int l, int r){
  5.     vector <bool> a(32);
  6.     for (int i=0; i<32; i++){
  7.         for (int j=l; j<r; j++){
  8.             if (bin[j][i]){
  9.                 a[i]=1;
  10.             }
  11.         }
  12.     }
  13.     return a;
  14. }
  15. bool bin_search(int n, int k, vector<vector<bool>> bin, int l){
  16.     int r=n;
  17.     while (r-l>1){
  18.         int m=(r+l)/2;
  19.         vector <bool> a;
  20.         a=count_(n, bin, l, m);
  21.         int sum;
  22.         for (int i=0; i<32; i++){
  23.             if (a[i]){
  24.                 sum+=(1<<(31-i));
  25.             }
  26.         }
  27.         if (sum>k){
  28.             r=m;
  29.         }else if (sum<k){
  30.             l=m;
  31.         }
  32.         else{
  33.             l=m;
  34.             return true;
  35.         }
  36.     }
  37.     return false;
  38. }
  39. int main(){
  40.     //freopen("or.in", "r", stdin);
  41.     //freopen ("or.out", "w", stdout);
  42.     int n, k;
  43.     cin>>n>>k;
  44.     vector <int> h(n);
  45.     for (int i=0; i<n; i++){
  46.         cin>>h[i];
  47.     }
  48.     vector <int> h2(n);
  49.     h2=h;
  50.     vector <vector<bool>> bin(n, vector <bool> (32));
  51.     for (int i=0; i<n; i++){
  52.         for (int j=31; j>=0; j--){
  53.             bin[i][j]=h2[i]/(1<<j);
  54.             if (bin[i][j]){
  55.                 h2[i]-=(1<<j);
  56.             }
  57.         }
  58.     }
  59.     bool a=0;
  60.     int l1;
  61.     for (int l=0; l<n; l++){
  62.         if (bin_search(n, k, bin, l)){
  63.             a=1;
  64.             l1=l;
  65.         }
  66.     }
  67.     if (a){
  68.         cout<<"YES"<<"\n";
  69.         cout<<l1;
  70.     }
  71.     else{
  72.         cout<<"NO";
  73.     }
  74. }
  75.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement