题目名称 2892. [2018多省省队联测] IIIDX
输入输出 iiidx.in/out
难度等级 ★★★☆
时间限制 2000 ms (2 s)
内存限制 512 MB
测试数据 20 简单对比
题目来源 2018-04-10
开放分组 全部用户
提交状态
分类标签
通过:2, 提交:4, 通过率:50%
GravatarHzoi_moyi 90 6.822 s C++
Gravatarsnake 0 0.110 s C++
关于 IIIDX 的讨论
输入数学公式,向下取整:\lfloor和\rfloor,分数:\frac{分子}{分母}。
GravatarWHZ0325
2018-04-11 19:23 1楼

2892. [2018多省省队联测] IIIDX

★★★☆   输入文件:iiidx.in   输出文件:iiidx.out   简单对比
时间限制:2 s   内存限制:512 MB

【题目背景】

Osu 听过没?那是 Konano 最喜欢的一款音乐游戏,而他的梦想就是有一天自己也 能做个独特酷炫的音乐游戏。现在,他在世界知名游戏公司 KONMAI 内工作,离他的 梦想也越来越近了。

这款音乐游戏内一般都包含了许多歌曲,歌曲越多,玩家越不易玩腻。同时,为了 使玩家在游戏上氪更多的金钱花更多的时间,游戏一开始一般都不会将所有曲目公开, 有些曲目你需要通关某首特定歌曲才会解锁,而且越晚解锁的曲目难度越高。

【题目描述】

这一天,Konano 接到了一个任务,他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有 $n$ 首曲目,每首曲目都会有一个难度 $d$,游戏内第 $i$ 首曲目会在玩家 Pass 第 $\lfloor\frac{i}{k}\rfloor$ 首曲目后解锁($\lfloor x\rfloor$ 为下取整符号)若 $\lfloor\frac{i}{k}\rfloor = 0$,则说明这首曲目无需解锁

举个例子:当 k = 2 时,第 1 首曲目是无需解锁的$\lfloor\frac{1}{2}\rfloor = 0$),第 7 首曲目需要玩家 Pass 第 $\lfloor\frac{7}{2}\rfloor = 3$ 首曲目才会被解锁。

Konano 的工作,便是安排这些曲目的顺序,使得每次解锁出的曲子的难度不低于作为条件需要玩家通关的曲子的难度,即使得确定顺序后的曲目的难度对于每个 $i$ 满足$d_i ≥d_{\lfloor\frac{i}{k}\rfloor}$。

当然这难不倒曾经在信息学竞赛摸鱼许久的 Konano。那假如是你,你会怎么解决这份任务呢?

【输入格式】

从文件 $iiidx.in$ 中读入数据。

第 $1$ 行 $1$ 个正整数 $n$ 和 $1$ 个小数 $k$,$n$ 表示曲目数量,$k$ 其含义如题所示。

第 $2$ 行 $n$ 个用空格隔开的正整数 $d$,表示这 $n$ 首曲目的难度。

【输出格式】

输出到文件 $iiidx.out$ 中。

输出 $1$ 行 $n$ 个整数,按顺序输出安排完曲目顺序后第 $i$ 首曲目的难度。

若有多解,则输出 $d_1$ 最大的;若仍有多解,则输出 $d_2$ 最大的,以此类推。

【样例输入】

4 2.0
114 514 1919 810

【样例输出】

114 810 514 1919

【子任务】