#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; }; |