#include <bits/stdc++.h> using namespace std; const int mxn = 1e6+6; int bitsPref[mxn]; int i = 1; // bs smallest number, that has at least LEFT bits to offer int findNext(int sum){ int p = 0; int k = i; int mid; int res = INT_MAX; while(p <= k){ mid = (p+k)/2; //cout<<"mid is "<<mid<<endl; if(bitsPref[mid] >= sum){ res = min(res, mid); k = mid - 1; }else{ p = mid + 1; } } return res; } vector<int > rrr; int main() { int n; scanf("%d",&n); while(bitsPref[i-1] <= n){ int b = __builtin_popcount(i); bitsPref[i] = bitsPref[i-1] + b; ++i; } /*for(int j = 0; j < 20; ++j){ cout<<bitsPref[j]<<" "; } cout<<endl; for(int j = 0; j <= n; ++j){ cout<<findNext(j)<<" "; }*/ while(n != 0){ int h = findNext(n); rrr.push_back(h); n -= __builtin_popcount(h); } printf("%d\n",rrr.size()); for(int j = 0; j < rrr.size(); ++j){ printf("%d ",rrr[j]); } 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 <bits/stdc++.h> using namespace std; const int mxn = 1e6+6; int bitsPref[mxn]; int i = 1; // bs smallest number, that has at least LEFT bits to offer int findNext(int sum){ int p = 0; int k = i; int mid; int res = INT_MAX; while(p <= k){ mid = (p+k)/2; //cout<<"mid is "<<mid<<endl; if(bitsPref[mid] >= sum){ res = min(res, mid); k = mid - 1; }else{ p = mid + 1; } } return res; } vector<int > rrr; int main() { int n; scanf("%d",&n); while(bitsPref[i-1] <= n){ int b = __builtin_popcount(i); bitsPref[i] = bitsPref[i-1] + b; ++i; } /*for(int j = 0; j < 20; ++j){ cout<<bitsPref[j]<<" "; } cout<<endl; for(int j = 0; j <= n; ++j){ cout<<findNext(j)<<" "; }*/ while(n != 0){ int h = findNext(n); rrr.push_back(h); n -= __builtin_popcount(h); } printf("%d\n",rrr.size()); for(int j = 0; j < rrr.size(); ++j){ printf("%d ",rrr[j]); } return 0; } |