QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 5167. 魔术师

统计

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

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

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

  1. 从牌叠顶部拿起一叠牌放到桌面上,称为牌叠 A(可以为空);
  2. 从牌叠顶部一张一张背面朝上往桌面上发 $m$ 张牌,得到牌叠 B;
  3. 将牌叠 B 放回牌堆顶部;
  4. 将牌叠 A 放回牌堆顶部。

请你帮助 King 给出一种操作方案,或告诉 King 不存在这样的操作方案。

输入格式

第一行三个整数 $T,n,m$,表示测试包编号、牌堆中牌的数量和每次操作发牌的数量。

第二行 $n$ 个整数 $p_1,p_2,\ldots,p_n$,表示自顶向下每张牌的编号。

输出格式

若不存在操作方案,输出 $-1$。否则:

第一行一个非负整数 $k$,表示操作次数。

接下来 $k$ 行,第 $i$ 行一个非负整数 $c_i\ (0\le c_i\le 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

评分方式

每个测试包附有参数 $lim_1,lim_2,\ldots,lim_5$。设一个测试包的分值为 $S$,对于该测试包内的测试点,评分方式如下:

  • 若该测试点无解:
    • 若选手输出有解,得 $0$ 分。
    • 否则得 $S$ 分。
  • 若该测试点有解: +若选手输出无解或选手的方案不合法,得 $0$ 分。 +否则设选手的方案操作次数为 $k$,则得分为 $$\frac{S}{5}\times \sum_{i=1}^{5}[k\le lim_i]$$

该测试包的得分为测试包内每个测试点得分的最小值。

数据范围

对于 $100\%$ 的数据,$1\le m\le n\le 1000$,$p$ 是一个 $1$ 到 $n$ 的排列。

对于有解的数据,数据生成方式为:确定 $n,m$ 后, $p$ 在有解的排列集合中随机生成。

各测试包的附加限制如下:

测试包编号 $n\le $ $m\in $ $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$ 为偶数。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

特别地,对于测试包 $1,2,11,12$,时间限制为 $2\texttt{s}$。