fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. bool isPowerOfTwo(int num) 
  6. {
  7.     if (num <= 0) return false;
  8.  
  9.     return (num & (num - 1)) == 0;
  10. }
  11.  
  12. bool isAllSet(int num)
  13. {
  14. 	if(isPowerOfTwo(num+1))
  15. 	{
  16. 		return true;
  17. 	}
  18. 	return false;
  19. }
  20.  
  21. int numberOfBits(int num)
  22. {
  23. 	int count = 0;
  24. 	while(num)
  25. 	{
  26. 		num >>= 1;
  27. 		count++;
  28. 	}
  29. 	return count;
  30. }
  31.  
  32. int binaryToDecimal(string& binaryStr) 
  33. {
  34.     int decimal = 0;
  35.     int length = binaryStr.length();
  36.  
  37.     for (int i = 0; i < length; ++i) 
  38.     {
  39.         if (binaryStr[i] == '1') 
  40.         {
  41.             decimal += pow(2, (length - i - 1));
  42.         }
  43.     }
  44.  
  45.     return decimal;
  46. }
  47.  
  48. int makeAllSetBits(int n)
  49. {
  50. 	string s = "";
  51. 	for(int i=0; i<n; i++)
  52. 	{
  53. 		s+='1';
  54. 	}
  55. 	return binaryToDecimal(s);
  56. }
  57.  
  58. vector<int> maximizeSetBits(int n, int k)
  59. {
  60. 	if(n==1)
  61. 	{
  62. 		return {k};
  63. 	}
  64.  
  65. 	if(n==2)
  66. 	{
  67. 		return {k, 0};
  68. 	}
  69.  
  70. 	if(isAllSet(k))
  71. 	{
  72. 		vector<int> answer(n, 0);
  73. 		answer[0] = k;
  74. 	}
  75.  
  76. 	if(isPowerOfTwo(k))
  77. 	{
  78. 		vector<int> answer(n, 0);
  79. 		answer[0] = k-1;
  80. 		answer[1] = 1;
  81. 	}
  82.  
  83. 	vector<int> answer(n);
  84. 	int digitsInBin = numberOfBits(k);
  85. 	int firstNumber = makeAllSetBits(digitsInBin-1);
  86. 	int secondNumber = k - firstNumber;
  87. 	answer[0] = firstNumber;
  88. 	answer[1] = secondNumber;
  89. 	return answer;
  90.  
  91. }
  92.  
  93. int main()
  94. {
  95. 	int t;
  96. 	cin >> t;
  97. 	while(t--)
  98. 	{
  99. 		int n, k;
  100. 		cin >> n >> k;
  101. 		vector<int> nums = maximizeSetBits(n, k);
  102. 		for(int num: nums)
  103. 		{
  104. 			cout << num << " ";
  105. 		}
  106. 		cout << endl;
  107. 	}
  108. 	return 0;
  109. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
4
1 5
2 3
2 5
6 51
stdout
copy 
5 
3 0 
5 0 
31 20 0 0 0 0
https://ideone.com/f4g1xI
problem BIT2, based on SPOJ submission 11034498 (C++ 4.3.2), 2014-02-09 15:54:15
language:
C++ (gcc 8.3)
created:
12 days 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!