[THUPC 2023 决赛] 喵了个喵 III

这个游戏有一个牌堆和 $n$ 个栈，任务是要通过游戏规则将所有的卡牌消去。开始时牌堆中有 $m$ 张卡牌，从上到下的图案分别是 $a_1,a_2,\cdots, a_m$。所有的卡牌一共有 $k$ 种图案，从 $1$ 到 $k$ 编号。牌堆中每一种图案的卡牌都有偶数张。开始时所有的栈都是空的。这个游戏有两种操作： - 选择一个栈，将牌堆顶上的卡牌放入栈的顶部。如果这么操作后，这个栈最上方的两张牌有相同的图案，则会自动将这两张牌消去。 - 选择两个不同的栈，如果这两个栈栈**顶**的卡牌有相同的图案，则可以将这两张牌消去。如果不同，则什么也不会做。 经过多次观察小 E 发现总是有 $n=2$ 和 $k=m/2$，即只有两个栈且每一种图案的卡牌都恰好有 $2$ 张。虽然如此，小 E 还是一直无法通关。请你帮小 E 设计一下游戏方案，即给出相应的操作序列使得小 E 可以把所有的卡牌消去。 ## Input 第一行一个正整数 $m$。 第二行 $m$ 个正整数，分别表示 $a_1,a_2,\cdots, a_m$。 保证 $1\sim m/2$ 在序列中各出现两次。 ## Output **本题采用 special judge**。 如果无解，输出一行 `No solution.`。 如果有解，第一行输出 `Cleared.`。第二行输出一个正整数 $op$，表示操作的次数。你需要保证 $m\le op\le 2m$。 接下来一行一个长度为 $op$ 的字符串，每一位是一个不超过 $2$ 的非负整数，按顺序表示进行的操作。若为 $1$ 或 $2$，则表示进行一次第一个操作并选择栈 $1$ 或栈 $2$。若为 $0$，则表示进行一次第二个操作。由于只有两个栈，所以你不需要输出额外的信息来说明你选择了哪些栈。 [samples] ## Background 小 E 玩腻了《喵了个喵》，于是决定换一款消除游戏来玩。然而小 E 发现市面上的消除游戏规则都差不多，比如这个游戏，它的规则和《喵了个喵》只有一个字不相同。虽然说，改了一个字的游戏就是新游戏，但确是缺了点意思。 ## Note ### 样例 1 解释 下图是初始状态。  下图是前两次操作之后的结果。   下图是第三次和第四次操作之后的结果。   下图是第五次操作之后的结果。   ### 数据规模与约定 - 保证 $2\le m \le 1500$ 且为偶数。 - 保证 $1\le a_i \le m/2$ 且每一种数在序列中出现恰好两次。 ### 评分方法 你的输出的第一行需要与标准答案一致。 若有解，且在按顺序进行所有操作后，牌堆为空且所有的栈均为空，则认为你的答案正确。 ### 后记 **以下部分与本题内容无关。** 说到底，那个嫌《喵了个喵 II》的题面太长的人其实是小 E 自己。它本来的题面中，题目背景和题目描述是这样的： 【题目背景】 小 E 玩腻了《喵了个喵》，于是决定换一款消除游戏来玩。然而小 E 发现市面上的消除游戏规则都差不多，比如这个游戏，它的规则和《喵了个喵》只有略微不相同。虽然说，只要改一个字就是新游戏，但确是缺了点意思。 【题目描述】 这个游戏有一个牌堆和 $n$ 个可以从栈底删除元素的栈，任务是要通过游戏规则将所有的卡牌消去。开始时牌堆中有 $m$ 张卡牌，从上到下的图案分别是 $a_1,a_2,\cdots, a_m$。所有的卡牌一共有 $k$ 种图案，从 $1$ 到 $k$ 编号。牌堆中每一种图案的卡牌都有偶数张。开始时所有的栈都是空的。这个游戏有两种操作： - 选择一个栈，将牌堆顶上的卡牌放入栈的顶部。 - 选择两个不同的栈，如果这两个栈栈**底**的卡牌有相同的图案，则可以将这两张牌消去，原来在栈底上方的卡牌会成为新的栈底。如果不同，则什么也不会做。 经过多次观察小 E 发现总是有 $n=2$ 和 $k=m/4$，并且每一种图案的卡牌都恰好有 $4$ 张。虽然如此，小 E 还是一直无法通关。请你帮小 E 设计一下游戏方案，即给出相应的操作序列使得小 E 可以把所有的卡牌消去。 ### 题目来源 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。 题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。