CF659C.Tanya and Toys

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

In Berland recently a new collection of toys went on sale. This collection consists of 109 types of toys, numbered with integers from 1 to 109. A toy from the new collection of the i-th type costs i bourles.

Tania has managed to collect n different types of toys _a_1, _a_2, ..., a__n from the new collection. Today is Tanya's birthday, and her mother decided to spend no more than m bourles on the gift to the daughter. Tanya will choose several different types of toys from the new collection as a gift. Of course, she does not want to get a type of toy which she already has.

Tanya wants to have as many distinct types of toys in her collection as possible as the result. The new collection is too diverse, and Tanya is too little, so she asks you to help her in this.

在贝尔兰,最近推出了一款全新的玩具系列。该系列包含 10910^9 种不同类型的玩具,编号为 11 到 10910^9 的整数。其中第 ii 种玩具的价格为 ii 博尔(bourles)。

塔尼娅已经从该新系列中收集到了 nn 种不同的玩具,其类型编号分别为 a1, a2, …, ana_1,\,a_2,\,\dots,\,a_n。今天是塔尼娅的生日,她的妈妈决定最多花费 mm 博尔为女儿购买生日礼物。塔尼娅将从该新系列中挑选若干种不同类型的玩具作为礼物。当然,她不希望收到自己已经拥有的玩具类型。

塔尼娅希望最终她的玩具收藏中不同种类的数量尽可能多。由于该新系列种类过于丰富,而塔尼娅年纪又太小,因此她请你来帮她解决这个问题。

输入格式

The first line contains two integers n (1 ≤ n ≤ 100 000) and m (1 ≤ m ≤ 109) — the number of types of toys that Tanya already has and the number of bourles that her mom is willing to spend on buying new toys.

The next line contains n distinct integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) — the types of toys that Tanya already has.

第一行包含两个整数 nn(1≤n≤100 0001 \leq n \leq 100\,000)和 mm(1≤m≤1091 \leq m \leq 10^9)——分别表示塔尼娅已拥有的玩具种类数,以及她妈妈愿意用于购买新玩具的布尔币数量。

下一行包含 nn 个互不相同的整数 a1, a2, ..., ana_1,\,a_2,\,...,\,a_n(1≤ai≤1091 \leq a_i \leq 10^9)——表示塔尼娅已拥有的玩具种类。

输出格式

In the first line print a single integer k — the number of different types of toys that Tanya should choose so that the number of different types of toys in her collection is maximum possible. Of course, the total cost of the selected toys should not exceed m.

In the second line print k distinct space-separated integers _t_1, _t_2, ..., t__k (1 ≤ t__i ≤ 109) — the types of toys that Tanya should choose.

If there are multiple answers, you may print any of them. Values of t__i can be printed in any order.

第一行输出一个整数 kk —— Tanya 应选择的不同类型玩具的种类数,使得她收藏中不同种类玩具的数量达到最大可能值。当然,所选玩具的总费用不能超过 mm。

第二行输出 kk 个互不相同的、以空格分隔的整数 t1, t2, …, tkt_1,\ t_2,\ \dots,\ t_k(1≤ti≤1091\le t_i\le 10^9)—— Tanya 应选择的玩具类型。

若存在多个答案,输出任意一个即可。tit_i 的值可以以任意顺序输出。

输入输出样例

  • 输入#1

    3 7
    1 3 4

    输出#1

    2
    2 5
  • 输入#2

    4 14
    4 6 12 8

    输出#2

    4
    7 2 3 1

说明/提示

In the first sample mom should buy two toys: one toy of the 2-nd type and one toy of the 5-th type. At any other purchase for 7 bourles (assuming that the toys of types 1, 3 and 4 have already been bought), it is impossible to buy two and more toys.

在第一个样例中,妈妈应购买两个玩具:一个第 2 类型的玩具和一个第 5 类型的玩具。在花费 7 博尔勒(假设第 1、3 和 4 类型的玩具已被购买)的其他任何购买方案中,都无法购买两个或更多玩具。

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

首页