题面下载

样例下载

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

曙梦研究院的算法演练室里有一台单行全息棋盘。最近，实习生小梦正在利用它进行一种黑白棋子的位移推演训练，以锻炼自己对复杂状态空间的搜索与规划能力。

题目描述

全息棋盘是一个规模为 $(n+m+1)\times 1$ 的棋盘，设格子从左到右的编号分别为 $1,2,\cdots, (n+m+1)$。

初始情况下，第 $1,\cdots,n$ 格均为白棋子，第 $n+1$ 格为空，第 $n+2,\cdots,n+m+1$ 格均为黑棋子。

小梦可以对棋盘进行操作，每次操作都可以将当前空格子左右半径 $2$ 格以内的一个棋子移动到空格子中。形式化地说：若当前第 $x$ 格为空，则可以将第 $x-2,x-1,x+1,x+2$ 格中的任意一枚棋子移动至第 $x$ 格（前提是对应格的编号在 $1,\cdots ,n+m+1$ 的范围内）。

现在要求最终局面为：第 $1,\cdots,m$ 格均为黑棋子，第 $m+1$ 格为空，第 $m+2,\cdots,n+m+1$ 格为白棋子。你需要帮助小梦算出最少的操作次数，并给出具体的操作序列。

输入格式

从标准输入读入数据。

输入第一行为两个正整数，分别为 $n,m$。

输出格式

输出到标准输出。

第一行为一个整数 $x$，表示从初始局面到最终局面所需要的最少操作步数。

第二行为 $x$ 个正整数 $c_1,\cdots,c_x$，各整数间以一个空格分隔。其中 $c_i$ 表示第 $i$ 次操作选择了第 $c_i$ 格的棋子移动至当前局面下的空格子。如果有多种解法，输出任意一种即可。

输入格式

从标准输入读入数据。

输入第一行为两个正整数，分别为 $n,m$。

输出格式

输出到标准输出。

第一行为一个整数 $x$，表示从初始局面到最终局面所需要的最少操作步数。

第二行为 $x$ 个正整数 $c_1,\cdots,c_x$，各整数间以一个空格分隔。其中 $c_i$ 表示第 $i$ 次操作选择了第 $c_i$ 格的棋子移动至当前局面下的空格子。如果有多种解法，输出任意一种即可。

2 2

8
2 4 5 3 1 2 4 3

样例 1 解释

具体挪动的步骤如下：

合法的操作方案不止一种，4 2 1 3 5 4 2 3 也是合法操作，输出这两种或者其他合法方案当中的任意一种均为正确。

子任务

对于所有数据，保证 $n\times m\le 10^5$。

评分方式

对于每个测试点，评分标准如下：

• 若标准输出的第一行与答案的第一行不一致，该测试点不得分；
• 若标准输出的第一行与答案的第一行相同，则获得该测试点 $50\%$ 的分数；
  • 需要注意的是，这种情况下需要程序在规定的时间/空间限制内正常运行结束才能获得对应分数；
  • 此外，由于判题需要，即便你只想回答第一行的问题 $x$，也请在第二行按照输出格式输出 $x$ 个任意整数（数据范围不得超过 int）；
• 在第一行比对正确后，我们会检查第二行给出的操作序列是否可以得到最终状态，若可以达到，则获得该测试点的全部分数。
• 需要注意的是，不要在输出格式之外输出任何多余内容，否则测试点不得分（但是行末空格是允许的）。