#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <chrono>
#include <functional>
#include <cstdlib>
using namespace std;
int getBitCount(int number)
{
int result = 0;
while (number > 0)
{
result += (number & 1);
number >>= 1;
}
return result;
}
int main()
{
const clock_t begin_time = clock();
ios::sync_with_stdio(false);
int n;
std::cin >> n;
std::vector<int> bitCounts;
std::vector<int> sums;
int currentNumber=0;
int sum=0;
do
{
int bitCount = getBitCount(currentNumber);
sum += bitCount;
bitCounts.push_back(bitCount);
sums.push_back(sum);
currentNumber++;
} while (sum < n);
int remainingSum = n;
std::vector<int> results;
for (; currentNumber>0; --currentNumber)
{
if (sums[currentNumber - 1] < remainingSum)
{
results.push_back(currentNumber);
remainingSum -= bitCounts[currentNumber];
}
}
std::cout << results.size() << "\n";
for (auto number: results)
std::cout << number << " ";
//std::cout << float(clock() - begin_time) / CLOCKS_PER_SEC << "\n";
return 0;
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include <iostream> #include <vector> #include <algorithm> #include <string> #include <map> #include <set> #include <chrono> #include <functional> #include <cstdlib> using namespace std; int getBitCount(int number) { int result = 0; while (number > 0) { result += (number & 1); number >>= 1; } return result; } int main() { const clock_t begin_time = clock(); ios::sync_with_stdio(false); int n; std::cin >> n; std::vector<int> bitCounts; std::vector<int> sums; int currentNumber=0; int sum=0; do { int bitCount = getBitCount(currentNumber); sum += bitCount; bitCounts.push_back(bitCount); sums.push_back(sum); currentNumber++; } while (sum < n); int remainingSum = n; std::vector<int> results; for (; currentNumber>0; --currentNumber) { if (sums[currentNumber - 1] < remainingSum) { results.push_back(currentNumber); remainingSum -= bitCounts[currentNumber]; } } std::cout << results.size() << "\n"; for (auto number: results) std::cout << number << " "; //std::cout << float(clock() - begin_time) / CLOCKS_PER_SEC << "\n"; return 0; }; |
English