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
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 1e6 + 1;
int n;
int zap[N_MAX];
vector<int> ilosc[16+1]; // liczby z dana iloscia zapalonych bitow
int kt = 2; // dla ktorego przekracza
int ile;
bool usu[N_MAX]; // czy usuniety

// dla 120206 suma zapalonych bitow przekracza 1e6; liczba ta ma 10 zapalonych bitow

int main(void)
{
    cin >> n;

    // liczenie
    zap[1] = 1;
    ilosc[1].push_back(1);
    for(; kt<1e6; ++kt){
        int amt = __builtin_popcount(kt);
        ilosc[amt].push_back(kt);
        zap[kt] = zap[kt-1] + amt;
        if(zap[kt] > n) break;
    }

    int to_less = zap[kt]; // do obnizenia
    ile = kt;
    while(to_less - n > 0){
        for(int i=to_less-n; i>=1; --i){
            if((int)ilosc[i].size() > 0){
                usu[ilosc[i][(int)ilosc[i].size()-1]] = true;
                ile--;
                to_less -= i;
                break;
            }
        }
    }

    cout << ile << '\n';
    for(int i=kt; i>=1; --i){
        if(!usu[i]) cout << i << ' ';
    }
    cout << '\n';
}