fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int calc(int n){
  4. 	int ans =0;
  5. 	if(n==0)
  6. 		return 0;
  7. 	else{
  8. 		while(n!=1){
  9. 			ans+= n%2;
  10. 			n=n/2;
  11. 		}
  12. 		ans+=1;
  13. 	}
  14. 	return ans;
  15. }
  16. int fun(int arr[],int x,int k,int n){
  17. 	int val=0;
  18. 	for(int i=1;i<=x;i++){
  19. 		val+=arr[i];
  20. 	}
  21. 	if(val>=k)
  22. 		return true;
  23. 	for(int i=x+1;i<=n;i++){
  24. 		val-=arr[i-x];
  25. 		val+=arr[i];
  26. 		if(val>=k)
  27. 			return true;
  28. 	}
  29. 	return false;
  30. }
  31.  
  32. int main(){
  33. 	ios_base::sync_with_stdio(0);
  34. 	cin.tie(0);
  35. 	cout.tie(0);
  36. 	int n,q;
  37. 	cin>>n>>q;
  38. 	int arr[100001];
  39. 	arr[0]=0;
  40. 	for(int i=1;i<=n;i++){
  41. 		int temp;
  42. 		cin>>temp;
  43. 		arr[i]=calc(temp);
  44. 	}	
  45. 	while(q--){
  46. 		int k;
  47. 		cin>>k;
  48. 		int ans=INT_MAX;
  49. 		int l=1,r=100000;
  50. 		while(l<=r){
  51. 			int mid =l+ ((r-l)/2);
  52. 			if( fun(arr,mid,k,n) ){
  53. 				ans=min(ans,mid);
  54. 				r=mid-1;
  55. 			}
  56. 			else	
  57. 				l=mid+1;
  58. 		}
  59. 		if(ans==INT_MAX)
  60. 			cout<<-1<<"\n";
  61. 		else	
  62. 			cout<<ans<<"\n";
  63. 	}
  64.  
  65.  
  66. }	
  67.  
Success #stdin #stdout 0s 4164KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UP65XF
language:
C++ (gcc 8.3)
created:
3 years 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!