#1703. 魔术师

    ID: 1703 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1056来源:qoj.ac数据:公开样例模拟枚举

魔术师

魔术师

题目描述

标题: 魔术师 - Problem - QOJ.ac 发布时间: 2022-2023 集训队互测 Round 12 (Nov 29, 2022)

#5167. 魔术师

Statistics

King 是一名魔术师,他总是能运用一些简单的原理完成一些不可思议的事情。

现在 King 手里有一叠背面向上的扑克牌,一共有 n 张。King 为每张牌都赋予了一个在 1 到 n 之间的独一无二的编号,初始时自顶向下第 i 张牌的编号为 pi。在变魔术时,King 会执行若干次操作,使得自顶向下的第 i 张牌编号恰好为 i。

为了使魔术效果更具欺骗性,King 只会做一些看上去平常的动作。我们略去魔术师的具体手法,King 一次操作可以简化为以下步骤:

  1. 从牌叠顶部拿起一叠牌放到桌面上,称为牌叠 A(可以为空);
  2. 从牌叠顶部一张一张背面朝上往桌面上发 m 张牌,得到牌叠 B;
  3. 将牌叠 B 放回牌堆顶部;
  4. 将牌叠 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