Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- vector <bool> count_(int n, vector<vector<bool>> bin, int l, int r){
- vector <bool> a(32);
- for (int i=0; i<32; i++){
- for (int j=l; j<r; j++){
- if (bin[j][i]){
- a[i]=1;
- }
- }
- }
- return a;
- }
- bool bin_search(int n, int k, vector<vector<bool>> bin, int l){
- int r=n;
- while (r-l>1){
- int m=(r+l)/2;
- vector <bool> a;
- a=count_(n, bin, l, m);
- int sum;
- for (int i=0; i<32; i++){
- if (a[i]){
- sum+=(1<<(31-i));
- }
- }
- if (sum>k){
- r=m;
- }else if (sum<k){
- l=m;
- }
- else{
- l=m;
- return true;
- }
- }
- return false;
- }
- int main(){
- //freopen("or.in", "r", stdin);
- //freopen ("or.out", "w", stdout);
- int n, k;
- cin>>n>>k;
- vector <int> h(n);
- for (int i=0; i<n; i++){
- cin>>h[i];
- }
- vector <int> h2(n);
- h2=h;
- vector <vector<bool>> bin(n, vector <bool> (32));
- for (int i=0; i<n; i++){
- for (int j=31; j>=0; j--){
- bin[i][j]=h2[i]/(1<<j);
- if (bin[i][j]){
- h2[i]-=(1<<j);
- }
- }
- }
- bool a=0;
- int l1;
- for (int l=0; l<n; l++){
- if (bin_search(n, k, bin, l)){
- a=1;
- l1=l;
- }
- }
- if (a){
- cout<<"YES"<<"\n";
- cout<<l1;
- }
- else{
- cout<<"NO";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement