fork download
copy 
  1.     #include <bits/stdc++.h>
  2.     #define ll long long
  3.     #define ull unsigned long long 
  4.     using namespace std;
  5.  
  6.     vector< vector<ull> > get_subsets(vector<ull> set)
  7.     {
  8.         vector< vector<ull> > sub;
  9.         vector<ull> e;
  10.         sub.push_back(e);
  11.         for (unsigned int i = 0; i < set.size(); i++) {
  12.             vector< vector<ull> > t = sub;
  13.             ull sz1=t.size();
  14.             for (ull j = 0; j < sz1; j++)
  15.                 t[j].push_back( set[i] );
  16.  
  17.             sz1=t.size();
  18.             for (ull j = 0; j <sz1; j++)
  19.                 sub.push_back(t[j] );
  20.         }
  21.         return sub;
  22.     }
  23.  
  24.     int main() {
  25.     	std::ios::sync_with_stdio(false);
  26.     	vector< vector<ull> > sub,sub1;
  27.     	vector<ull> set,set1;
  28.     	int n;
  29.     	cin>>n;
  30.     	ull count=0,c=0,val,k;
  31.     	cin>>k;
  32.     	for(int i=0;i<n;i++){
  33.     		cin>>val;
  34.     		if(val==1)
  35. 				c++;
  36.     		else if(i<=n/2){
  37.     			set1.push_back(val);
  38.     		}
  39.     		else{
  40. 				set.push_back(val);
  41. 			}
  42.     	}
  43.  
  44.     	sort(set.begin(),set.end());
  45.  
  46.     	sort(set1.begin(),set1.end());
  47.  
  48.     	sub=get_subsets(set);
  49.     	sub1=get_subsets(set1);
  50.     	ull sz1=sub.size(),sz2=sub1.size();
  51.     	vector<ull> pro1,pro2;
  52.     	ull p=1;
  53.     	for(ull i=0;i<sz1;i++)
  54.     	{
  55. 			p=1;
  56.     		vector<ull> x=sub[i];
  57.     		ull sz3=x.size();
  58.     		for(ull j=0;j<sz3;j++)
  59.     		{
  60.     			//p*=x[j];
  61.     			ull a=p;
  62.     			p=a*x[j];
  63.     			if (p/a!=x[j]) {
  64. 					p=k+1;
  65. 					count++;
  66. 					break;
  67. 				}
  68.     			if(p>k){
  69.     				count++;		
  70.     				break;
  71.     			}
  72.     		}
  73.     		if(x.size()>0){
  74. 	//			cout<<"Product1  "<<p<<endl;
  75. 				pro1.push_back(p);
  76. 			}
  77.  
  78.     	}
  79.    // 	cout<<count<<endl;
  80.     	for(ull i=0;i<sz2;i++)
  81.     	{
  82. 			p=1;
  83.     		vector<ull> x=sub1[i];
  84.     		ull sz3=x.size();
  85.     		for(ull j=0;j<sz3;j++)
  86.     		{
  87. 				ull a=p;
  88.     			p=a*x[j];
  89.     			if ( p/a!=x[j]) {
  90. 					p=k+1;
  91. 					count++;
  92. 					break;
  93. 				}
  94.     			if(p>k){
  95.     				count++;
  96.     				break;
  97.     			}
  98.     		}
  99.     		if(x.size()>0){
  100. 	//			cout<<"Product2  "<<p<<endl;
  101. 				pro2.push_back(p);
  102. 			}
  103.     		p=1;
  104.     	}
  105.     //	cout<<count<<endl;
  106.  
  107.  
  108.     	sort(pro1.begin(),pro1.end());
  109.     	sort(pro2.begin(),pro2.end());
  110.  
  111.  
  112.     	ull m=pro1.size();
  113.     	ull n1=pro2.size();
  114. 		for(ull i=0;i<m;i++){
  115. 			for(ull j=0;j<n1;j++){
  116. 				ull a=pro1[i]*pro2[j];
  117.     			if ( a/pro1[i]!= pro2[j]) {
  118. 					count+=(n1-j);
  119. 					break;
  120. 				}
  121. 				else if(a>k){
  122. 					count+=(n1-j);
  123. 					break;
  124. 				}
  125.  
  126. 			}
  127. 		}
  128.  
  129. 		count+=(count*c);
  130. 		//cout<<count<<endl;
  131.     	cout<<(1<<n)-(count+1)<<endl;
  132.     	return 0;
  133.     } 
  134.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
3 4
1 2 3
stdout
copy 
5
https://ideone.com/XMBnDr
language:
C++ (gcc 8.3)
created:
6 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!