#P13724. 魔法照片

提交6 通过1
通过率16.7%
时间限制1000ms
内存限制256MiB
    ID: 13724 传统题 1000ms 256MiB 尝试: 6 已通过: 1 难度: 普及- 上传者: 标签>基础语法一维数组结构体基础算法自定义排序模拟

题目描述

题目背景

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

题目描述

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

请依次执行下面的过程:

  1. 按初始权值从大到小进行第一次排序;如果权值相同,编号较小的人排在前面。
  2. 第一次排序后,排在第 DD 位的人被分到第C=(D1)mod10+1C=(D-1)\bmod 10+1 类,其中 1C101\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

数据范围与约定

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