fork download
copy 
  1. #include<iostream>
  2. #include<cmath>
  3. #include<algorithm>
  4. #include<vector>
  5. #include<queue>
  6. using namespace std;
  7.  
  8. int main()
  9. {
  10. 	int test;
  11. 	cin>>test;
  12. 	int sum[100001],subsum[100001],orig[100];
  13. 	while(test--)
  14. 	{
  15. 	int n,m;
  16. 	cin>>m;
  17. 	n=pow(2,m);
  18. 	queue<int>q;
  19.  
  20. 	int i,idx=0;
  21. 	int ans=0;
  22.  
  23. 	for(i=0;i<n;i++)
  24. 	 cin>>sum[i];
  25.  
  26. 	sort(sum,sum+n);
  27. 	if(n==2)
  28. 	 cout<<sum[1];
  29. 	 else
  30. 	 {
  31. 	orig[ans++]=sum[1];
  32. 	orig[ans++]=sum[2];
  33.  
  34. 	subsum[idx++]=sum[1];
  35. 	subsum[idx++]=sum[2];
  36. 	subsum[idx++]=sum[1]+sum[2];
  37.  
  38. 	q.push(sum[1]+sum[2]);
  39.  
  40. 	for(i=3;i<n;i++)
  41. 	{
  42. 		if(!q.empty() && sum[i]==q.front())
  43. 		 	q.pop();
  44.  
  45. 		 else
  46. 		 {
  47. 		    orig[ans++]=sum[i];
  48. 		 	subsum[idx++]=sum[i];
  49. 		 	// generate all subsets
  50. 		 	int size=idx;
  51. 		 	for(int k=0;k<size-1;k++)
  52. 		 	{
  53. 		 		subsum[idx++]=sum[i]+subsum[k];
  54. 		 		//cout<<"going in queue : "<<sum[i]+subsum[k]<<endl;
  55. 		 		q.push(sum[i]+subsum[k]);
  56. 		 	}
  57.  
  58. 		 }
  59. 	}
  60. 	for(i=0;i<ans-1; i++)
  61. 	 cout<<orig[i]<<" ";
  62. 	 }
  63. 	 if(ans-1>=0)
  64. 	 cout<<orig[ans-1];
  65. 	 cout<<endl;
  66. 	}
  67. 	return 0;
  68. }
Success #stdin #stdout 0s 4144KB
comments (?)
stdin
copy 
1
3
0 2 3 5 5 7 8 10
stdout
copy 
2 3 5
https://ideone.com/sQbNRz
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!