1 second
256 megabytes
standard input
standard output
At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite set of Picks.
Fortunately, Picks remembers something about his set S:
- its elements were distinct integers from 1 to limit;
-
the value of
was
equal to sum; here lowbit(x) equals 2k where k is
the position of the first one in the binary representation of x. For example, lowbit(100102) = 102, lowbit(100012) = 12, lowbit(100002) = 100002 (binary
representation).
Can you help Picks and find any set S, that satisfies all the above conditions?
The first line contains two integers: sum, limit (1 ≤ sum, limit ≤ 105).
In the first line print an integer n (1 ≤ n ≤ 105),
denoting the size of S. Then print the elements of set S in
any order. If there are multiple answers, print any of them.
If it's impossible to find a suitable set, print -1.
5 5
2 4 5
4 3
3 2 3 1
5 1
-1
In sample test 1: lowbit(4) = 4, lowbit(5) = 1, 4 + 1 = 5.
In sample test 2: lowbit(1) = 1, lowbit(2) = 2, lowbit(3) = 1, 1 + 2 + 1 = 4.
贪心……从第一位向上贪心，然后每次往上合并。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int bh[20][100010],fa[20][100010],gs[20];
int pre[100010];
int n,limt,sum,ans[100010];
int getw(int x)
{
int res=0;
while(x)
{
x=x>>1;res++;
}
return res-1;
}
void solve()
{
int i,j;
for(i=0;i<=18;i++)
{
if((1<<i) & sum)
{
if(gs[i]>0)
{
for(j=bh[i][gs[i]];j;j=pre[j]) ans[++ans[0]]=j;
gs[i]--;
}
else {printf("-1\n");return;}
}
for(j=1;j<=gs[i];j+=2)
{
if(j+1<=gs[i])
{
pre[fa[i][j+1]]=bh[i][j];
gs[i+1]++;bh[i+1][gs[i+1]]=bh[i][j+1];fa[i+1][gs[i+1]]=fa[i][j];
}
}
}
printf("%d\n",ans[0]);
for(i=1;i<=ans[0];i++) printf("%d ",ans[i]);
}
int main()
{
int i,x,y;
cin>>sum>>limt;
for(i=1;i<=limt;i++)
{
x=(i & (-i));
y=getw(x);
gs[y]++;
fa[y][gs[y]]=i;bh[y][gs[y]]=i;
}
solve();
return 0;
}