AdditionalFile4904.zip

P5967 [POI 2016] Korale

题目描述

有 $n$ 个带标号的珠子，第 $i$ 个珠子的价值为 $a_i$。

现在你可以选择若干个珠子组成项链（也可以一个都不选），项链的价值为所有珠子的价值和。

给出所有可能的项链排序，先按权值从小到大排序，对于权值相同的，根据所用珠子集合的标号的字典序从小到大排序。

请输出第 $k$ 小的项链的价值，以及所用的珠子集合。

输入格式

第一行包含两个正整数 $n,k$。 第二行包含 $n$ 个正整数，依次表示每个珠子的价值 $a_i$。

输出格式

第一行输出第 $k$ 小的项链的价值。 第二行按标号从小到大依次输出该项链里每个珠子的标号。

输入输出样例 #1

输入 #1

4 10
3 7 4 3

输出 #1

10
1 3 4

说明/提示

对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le k\le \min(2^n,10^6)$，$1\le a_i\le 10^9$。

#4904. 「POI2016 R1」项链 Necklace

标签: 传统 | 时间限制: 5000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXIII Olimpiada Informatyczna — I etap Korale

Bajtyna 有 $n$ 颗编号从 $1$ 到 $n$ 的珠子，每颗都不相同，且各有其价值（以字节币计价）。她想用这些珠子制作一条项链，但可选的组合方式有很多。若两条项链使用的珠子集合不同，就算不同。为了方便选择，Bajtyna 决定给所有可能的项链组合排序。

排序的首要标准是项链中珠子的总价值，总价值越大，排名越靠后。若两个组合的总价值相同，则按珠子编号升序排列后的列表进行字典序比较*。

例如，假设有四颗珠子，价值依次为（按编号）$3,7,4,3$ 字节币，可组成 $16$ 种项链。以下是按 Bajtyna 规则排序的组合：

字节娜想知道第 $k$ 个组合的项链是怎样的。请你帮她设计！

输入格式

输入第一行包含两个正整数 $n$ 和 $k$，分别表示珠子数量和目标组合的排名。

第二行包含 $n$ 个正整数 $a_{1}, a_{2}, \ldots, a_{n}$，表示各珠子的价值。

保证存在至少 $k$ 种不同的项链组合。

输出格式

第一行输出一个整数，表示目标组合中珠子的总价值。

第二行输出目标项链使用的珠子编号，按升序排列，数字间用空格分隔。若 $k=1$，第一行输出 $0$，第二行留空。

样例

输入

4 10
3 7 4 3

输出

10
1 3 4

附加样例

1. $n=10$，所有珠子价值为 $1$；
2. $n=9$，珠子价值为 $2$ 的连续幂次；
3. $n=11$，一个珠子价值 $1$，十个价值 $10^{9}$，答案使用全部 $11$ 颗珠子；
4. $n=1000000, k=10$，珠子价值依次为 1 到 1000000。

数据范围与提示

所有子任务满足 $n, k \leq 1000000$ 且 $a_{i} \leq 10^{9}$。

若第一行（总价值）正确但第二行错误，可获该测试点一半分数（即使第二行缺失或多输出）。

详细子任务附加限制及分值如下表所示。