CF437B.The Child and Set

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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 2_k_ 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?

在儿童节,一个孩子来到 Picks 家中,把他的房子弄得一团糟。Picks 对此非常生气。许多重要的东西都丢失了,尤其是 Picks 最喜欢的集合 $ S $。

幸运的是,Picks 还记得关于他的集合 $ S $ 的一些信息:

  • 集合中的元素是 $ 1 $ 到 $ \text{limit} $ 之间的互不相同的整数;
  • 表达式 $ \sum_{x \in S} \text{lowbit}(x) $ 的值等于 $ \text{sum} $;其中 $ \text{lowbit}(x) $ 定义为 $ 2^k ,, k $ 是 $ x $ 的二进制表示中最低位 $ 1 $ 所在的位置(从右往左,从 $ 0 $ 开始计数)。例如:
    $ \text{lowbit}(10010_2) = 10_2 ,, \text{lowbit}(10001_2) = 1_2 ,, \text{lowbit}(10000_2) = 10000_2 $(括号内为二进制表示)。

你能帮助 Picks 找出任意一个满足上述所有条件的集合 $ S $ 吗?

输入格式

The first line contains two integers: sum, limit (1 ≤ sum, limit ≤ 105).

第一行包含两个整数:sum 和 limit(1 ≤ sum, limit ≤ 10⁵)。

输出格式

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.

第一行输出一个整数 nn(1≤n≤1051 \leq n \leq 10^5),表示集合 SS 的大小。随后以任意顺序输出集合 SS 的所有元素。若存在多个可行答案,输出任意一个即可。

若不存在满足条件的集合,则输出 −1-1。

输入输出样例

  • 输入#1

    5 5

    输出#1

    2
    4 5
  • 输入#2

    4 3

    输出#2

    3
    2 3 1
  • 输入#3

    5 1

    输出#3

    -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.

在样例测试 1 中:lowbit(4)=4\text{lowbit}(4) = 4,lowbit(5)=1\text{lowbit}(5) = 1,4+1=54 + 1 = 5。

在样例测试 2 中:lowbit(1)=1\text{lowbit}(1) = 1,lowbit(2)=2\text{lowbit}(2) = 2,lowbit(3)=1\text{lowbit}(3) = 1,1+2+1=41 + 2 + 1 = 4。

输入解题思路,AI测评打分。不知道怎么写?

首页