#P11773. 巅峰手速

    ID: 10458 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>洛谷原创Special JudgeO2优化构造洛谷月赛

巅峰手速

题目背景

“老妹儿啊,今天该你做家务吧……”

龙牙哥于是自愿体验了阿绫为他量身定制的游戏,把做家务的命运推上赌桌——

题目描述

阿绫给了龙牙哥 nn 张卡牌,它们已经整齐码在了桌上,从左至右第 ii 张的卡牌上的数字为 aia_i,龙牙哥需要通过一系列操作让卡牌上的数字从左至右不降。每次操作中,他可以抽出从左至右第 kkkk 为给定常数)张卡牌,然后将它放在这些牌的最左侧或最右侧。请帮助龙牙判断自己是否有可能完成目标,如果能,请顺便告诉他一种比较简单的操作方案。

输入格式

首先输入一个整数 TT,表示数据组数。

对于每组数据,输入两行:

第一行为两个整数 n,kn,k,分别表示卡牌数量和给定常数。

第二行为 nn 个整数,第 ii 个数表示第 ii 卡片上的数字 aia_i

输出格式

对于每组数据,输出若干行。格式如下:

  • 若龙牙哥无法完成目标,只输出一行 No

  • 若他能够完成目标,先输出一行 Yes,然后若干行形如 l cr c,表示他连续做了 c 次将第 kk 张卡牌放到最左侧或最右侧的操作。最后再输出一个 o,表示操作结束。

你的得分将与操作方案的行数(而非操作次数)有关。(详见得分计算方式

5
3 2
3 2 1
7 3
4 1 3 2 5 7 6
3 3
2 1 3
7 5
1 2 3 4 5 6 7
6 4
1 1 4 5 1 4
Yes
l 1
r 1
l 1
o
No
No
Yes
o
Yes
r 1
l 1
o

提示

样例解释

对于第一组样例:

将第二张卡牌(22)放到最左侧,卡牌数字变为 2,3,12,3,1
将第二张卡牌(33)放到最右侧,卡牌数字变为 2,1,32,1,3
将第二张卡牌(11)放到最左侧,卡牌数字变为 1,2,31,2,3

此时卡牌上的数字不降,操作结束。

得分计算方式

在一个测试数据中,是否有解判断正确可获得 20%20\% 的分数。如果操作方案也正确,则会跟据操作方案的行数(不包含最后一行的 o)按下表得分。

行数 得分
>7n>7n 40%40\%
7n\le7n 60%60\%
5n\le5n 80%80\%
3n\le3n 100%100\%

一个测试点的得分是其中每组测试数据得分的最小值。

注意事项

为了方便选手调试,本题下发了校验器用于本地自测校验得分,使用方法见后。需要注意下发的校验器与实际使用校验器的可能并不相同。我们保证实际使用的校验器在输出的操作序列行数不超过 7n7n 的情况下用时不超过 500ms。

如果输出格式有误,你将会获得 00 分。因此,如果你会判断是否有解但无法给出操作方案,也需要在判断有解后输出一行 o 表示操作结束。

为了避免无意义的反复操作,你需要保证每一次操作均有 1cn1\leq c \leq n,否则将会获得 00 分。

校验器使用方法

下载文件 testlib.hchecker.cpp 并将其置于同一文件夹。在该目录下运行命令 g++ checker.cpp -o checker -std=c++14 编译得到可执行文件 checker.exe (windows) / checker (linux)。

假如自测输入为 in.txt,程序输出为 out.txt。由于校验器无法判断是否有解,你需要创建一个答案文件(假如叫作 ans.txt),并在其中每行一个地写入每组数据的有解情况。例如对于样例,答案文件应为

Yes
No
No
Yes
Yes

将上述提到的输入、输出、答案三个文件与刚刚编译出来的校验器可执行文件置与同一文件夹。

  • 如果是 Windows Powershell,输入 .\checker.exe in.txt out.txt ans.txt

  • 如果是 Linux 终端,输入 ./checker in.txt out.txt ans.txt

校验器有三种可能的输出:wrong answer / ok / points x,分别表示对于该测试点你没有分 / 满分 / 获得了占比为 x 的分。

数据规模与约定

本题采用捆绑测试并开启所有合理的子任务依赖

对于 100%100\% 的数据,1T1051\le T\le10^51kn2×1051\le k\le n\le 2\times10^5n5×105\sum n\le5\times10^{5}1ai1091\le a_i\le 10^9

对于不同的子任务,作如下约定:

子任务编号 nn kk 子任务分值
11 =5=5 [1,n]\in[1,n] 1010
22 200\le200 4040
33 2×105\le2\times10^5 =2=2 2020
44 [1,n]\in[1,n] 3030