P13724. 魔法照片

提交6 通过2
通过率33.3%
时间限制1000ms
内存限制256MiB

题目描述

题目背景

有 nn 个人希望获得照片,但照片数量有限,只能选出最终排名最靠前的 kk 人。每个人先有一个基础权值,随后还会根据第一次排名得到额外权值。

题目描述

所有人按照 11 到 nn 编号,第 ii 个人的初始权值为 WiW_i。

请依次执行下面的过程:

  1. 按初始权值从大到小进行第一次排序;如果权值相同,编号较小的人排在前面。
  2. 第一次排序后,排在第 DD 位的人被分到第C=(D−1) mod 10+1C=(D-1)\bmod 10+1 类,其中 1≤C≤101\le C\le 10。
  3. 第 CC 类的人获得额外权值 ECE_C,因此其新权值变为原权值加 ECE_C。
  4. 按新权值从大到小再次排序;新权值相同时,编号较小的人排在前面。

输出第二次排序后前 kk 个人的原始编号。

输入格式

第一行两个整数 n,kn,k,分别表示总人数和需要选出的人数。

第二行包含 1010 个正整数 E1,E2,…,E10E_1,E_2,\ldots,E_{10},表示十个类别分别增加的权值。

第三行包含 nn 个正整数 W1,W2,…,WnW_1,W_2,\ldots,W_n,其中 WiW_i 是编号为 ii 的人的初始权值。

输出格式

输出一行 kk 个整数,依次为最终排名前 kk 的人的编号。相邻编号之间用一个空格分隔。

输入样例 #1

5 3
10 9 8 7 6 5 4 3 2 1
100 99 98 97 96

输出样例 #1

1 2 3

样例说明 #1

第一次排序后的编号依次为 1,2,3,4,51,2,3,4,5,五人分别获得 10,9,8,7,610,9,8,7,6 的额外权值。第二次排序后前三名仍为编号 1,2,31,2,3。

输入样例 #2

10 3
9 12 37 14 8 18 42 6 42 2
2 5 3 10 5 3 2 2 1 1

输出样例 #2

7 9 5

输入样例 #3

11 11
10 10 10 10 10 10 10 10 10 10
17 80 81 63 52 31 69 96 76 75 37

输出样例 #3

8 3 2 9 10 7 4 5 11 6 1

数据范围与约定

  • 1≤n≤200001\le n\le 20000;
  • 1≤k≤n1\le k\le n;
  • EiE_i 和 WiW_i 均为正整数;
  • 初始权值、增加后的权值以及相关计算结果均在 32 位有符号整数范围内。