题目详情题解（0）讨论（0）提交记录（0）

AT_agc001_f.[AGC001F] Wide Swap

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 NN 的数列 P1…PNP_1\ldots P_N，该数列是 1∼N1\sim N 的一个排列。

你可以对该数列进行如下操作任意次：

  • 选择整数 i,ji, j，满足 1≤i<j≤N1 \leq i < j \leq N。
  • 交换 PiP_i 和 PjP_j 的值。
  • 但必须满足 j−i≥Kj - i \geq K 且 ∣Pi−Pj∣=1|P_i - P_j| = 1。

请你求出通过上述操作能够得到的字典序最小的数列。

输入格式

输入以如下格式从标准输入读入：

NN KK P1P_1 P2P_2 ...... PNP_N

输出格式

输出通过题目中操作能够得到的字典序最小的数列。

输入输出样例

  • 输入#1

    4 2
4 2 3 1

    输出#1

    2
1
4
3

  • 输入#2

    5 1
5 4 3 2 1

    输出#2

    1
2
3
4
5

  • 输入#3

    8 3
4 5 7 8 3 1 2 6

    输出#3

    1
2
6
7
5
3
4
8

说明/提示

限制条件

  • 2≤N≤500, ⁣0002 \leq N \leq 500,\!000
  • 1≤K≤N−11 \leq K \leq N-1
  • PP 是 1,2,...,N1, 2, ..., N 的一个排列。

样例解释 1

可以按如下步骤进行操作：

  • 4 2 3 14\ 2\ 3\ 1
  • 4 1 3 24\ 1\ 3\ 2
  • 3 1 4 23\ 1\ 4\ 2
  • 2 1 4 32\ 1\ 4\ 3

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页