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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// Jan Burdzicki
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5 + 5;

void solve()
{
	int suma_ilosci_bitow_zapalonych;
	cin >> suma_ilosci_bitow_zapalonych;

	vector <int> ilosc_bitow(MAX_N);

	for(int i = 1; i < MAX_N; i++)
	{
		ilosc_bitow[i] = __builtin_popcount(i);
	}

	vector <int> sumy_prefiksowe(MAX_N);

	for(int i = 1; i < MAX_N; i++)
	{
		sumy_prefiksowe[i] = sumy_prefiksowe[i - 1] + ilosc_bitow[i];
	}

	int indeks = 0;

	while(sumy_prefiksowe[indeks] < suma_ilosci_bitow_zapalonych)
	{
		indeks++;
	}

	vector <bool> czy_bierzemy(indeks + 1, true);

	czy_bierzemy[0] = false;

	int wynik = indeks;

	int obecna_ilosc_bitow = sumy_prefiksowe[indeks];

	for(int i = indeks; i >= 1; i--)
	{
		if(suma_ilosci_bitow_zapalonych <= obecna_ilosc_bitow - ilosc_bitow[i])
		{
			obecna_ilosc_bitow -= ilosc_bitow[i];

			czy_bierzemy[i] = false;

			wynik--;
		}
	}

	cout << wynik << "\n";

	for(int i = indeks; i >= 1; i--)
	{
		if(czy_bierzemy[i])
		{
			cout << i << " ";
		}
	}

	cout << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
	// cin >> t;

	while(t--)
	{
		solve();
	}

	return 0;
}