#1703. 魔术师
魔术师
魔术师
题目描述
标题: 魔术师 - Problem - QOJ.ac 发布时间: 2022-2023 集训队互测 Round 12 (Nov 29, 2022)
#5167. 魔术师
King 是一名魔术师,他总是能运用一些简单的原理完成一些不可思议的事情。
现在 King 手里有一叠背面向上的扑克牌,一共有 n 张。King 为每张牌都赋予了一个在 1 到 n 之间的独一无二的编号,初始时自顶向下第 i 张牌的编号为 pi。在变魔术时,King 会执行若干次操作,使得自顶向下的第 i 张牌编号恰好为 i。
为了使魔术效果更具欺骗性,King 只会做一些看上去平常的动作。我们略去魔术师的具体手法,King 一次操作可以简化为以下步骤:
- 从牌叠顶部拿起一叠牌放到桌面上,称为牌叠 A(可以为空);
- 从牌叠顶部一张一张背面朝上往桌面上发 m 张牌,得到牌叠 B;
- 将牌叠 B 放回牌堆顶部;
- 将牌叠 A 放回牌堆顶部。
请你帮助 King 给出一种操作方案,或告诉 King 不存在这样的操作方案。
输入格式
第一行三个整数 T,n,m,表示测试包编号、牌堆中牌的数量和每次操作发牌的数量。
第二行 n 个整数 p1,p2,…,pn,表示自顶向下每张牌的编号。
输出格式
若不存在操作方案,输出 −1。否则:
第一行一个非负整数 k,表示操作次数。
接下来 k 行,第 i 行一个非负整数 ci (0≤ci≤n−m),表示第 i 次操作的牌叠 A 中牌的数量。
样例 1 输入
0 8 4
6 2 5 1 7 4 3 8
样例 1 输出
4
0
2
3
1
样例 2 输入
0 6 5
3 4 1 5 6 2
样例 2 输出
-1
评分方式
每个测试包附有参数 lim1,lim2,…,lim5。设一个测试包的分值为 S,对于该测试包内的测试点,评分方式如下:
-
若该测试点无解:
- 若选手输出有解,得 0 分。
- 否则得 S 分。
-
若该测试点有解: +若选手输出无解或选手的方案不合法,得 0 分。 +否则设选手的方案操作次数为 k,则得分为
S5×∑i=15[k≤limi]
该测试包的得分为测试包内每个测试点得分的最小值。
数据范围
对于 100% 的数据,1≤m≤n≤1000,p 是一个 1 到 n 的排列。
对于有解的数据,数据生成方式为:确定 n,m 后, p 在有解的排列集合中随机生成。
各测试包的附加限制如下:
测试包编号 n≤ m∈ lim= 分值 1 10 [1,n] {50,200,500,2000,10000} 5 2 {120,300,1000,3000,10000} 3 30.h=2 {1000,30000,60000,300000,1000000} 4 {2500,50000,110000,300000,1000000} 5 50 {3000,25000,150000,500000,1000000} 15 6 {6000,50000,300000,700000,1500000} 5 7 200 {20000,50000,200000,500000,1000000} 8 {40000,100000,300000,700000,1500000} 9 1000 [4,5] {70000,150000,300000,700000,1500000} 10 {100000,200000,400000,800000,1500000} 11 [6,8] {50000,100000,200000,500000,1000000} 12 {60000,120000,250000,500000,1000000} 13 [40,60] {10000,25000,50000,200000,1000000} 14 {12000,30000,60000,200000,1000000} 15 [1,n] {450000,700000,950000,1250000,1500000} 15 16 {1000000,1200000,1600000,2200000,2500000} 5
对于编号为奇数的测试包,保证 m 为奇数;对于编号为偶数的测试包,保证 m 为偶数。
时间限制:1s
空间限制:512MB
特别地,对于测试包 1,2,11,12,时间限制为 2s。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
0 8 4
6 2 5 1 7 4 3 8
4
0
2
3
1
样例 2
0 6 5
3 4 1 5 6 2
-1