[POI 2010] ZAB-青蛙

题目描述

在一条笔直且很长的 Byteotian 小溪河床上，有 $n$ 块露出水面的石头，它们到小溪源头的距离依次为 $p_1 < p_2 < \cdots < p_n$。 一只小青蛙正坐在其中一块石头上，准备开始跳跃训练。

每次跳跃时，青蛙都会跳到距离它当前所在石头第 $k$ 近的那块石头上。 具体规则： 如果青蛙在石头 $p_i$ 上，它会跳到满足以下条件的石头 $p_j$ 上：

1. 到 $p_i$ 的距离严格小于 $p_j$ 到 $p_i$ 距离的石头数量 不超过 $k$；
2. 到 $p_i$ 的距离小于等于 $p_j$ 到 $p_i$ 距离的石头数量 大于 $k$。

如果满足条件的石头 $p_j$ 不唯一，青蛙会选择最靠近源头（编号最小）的那块。

请你计算：青蛙从每一块石头出发，跳跃 $m$ 次后，最终会停在哪块石头上？

输入格式

第一行：三个整数 $n, k, m$

• $n$：石头数量
• $k$：跳跃规则参数
• $m$：跳跃次数（$1 \le m \le 10^{18}$）

第二行：$n$ 个严格递增的整数 $p_1,p_2,\dots,p_n$，表示石头的位置

输出格式

一行 $n$ 个整数 $r_1,r_2,\dots,r_n$ $r_i$ 表示从第 $i$ 块石头出发，跳 $m$ 次后停留的石头编号

输入样例1：

5 2 4
1 2 4 7 10

输出样例1：

1 1 3 1 1

提示

样例 #1 解释

图中展示了青蛙从每块石头出发，单次跳跃会跳到的位置。

标签：P3509|动态规划 DP|2010|倍增|单调队列|POI（波兰）|深度优先搜索 DFS

来源

P3509|[POI 2010] ZAB-Frog