#P17505. [ICPC 2026 Wuhan I] Iroha and the Kingdom of Construction
[ICPC 2026 Wuhan I] Iroha and the Kingdom of Construction
题目描述
兜兜转转,彩叶来到了月读空间里的一个神秘地界 — 构造王国。
听闻你曾经来过此处,彩叶非常开心,并向你分享了她在构造王国中一段有趣的记忆。
构造王国中有一副神奇的纸牌,它有恰好 种不同点数(依次用 到 之间的整数表示),每种点数恰好有两张。经过均匀洗牌,这 张纸牌构成了一幅牌堆。换句话说:输入数据保证,牌堆是由所有包含 种点数、每种恰好两张牌的合法牌堆中等概率随机生成的。
在这个空间中,彩叶被赋予了一个很强大的能力:生成栈。由于这项能力十分消耗体力,彩叶只能生成 个栈。
现在,彩叶需要按照从上到下的顺序依次取出初始牌堆中的牌。对于每张被取出的牌,彩叶可以将其放入任意一个栈中。
当所有的 张牌都放置完毕后,彩叶的栈需要满足以下条件:可以进行若干次如下的 “消除操作”,直到所有牌均被消除完毕:
- 每次操作选择两个不同的栈,若这两个栈当前的栈顶卡牌点数相同,则将这两张牌同时弹出(删除)。
很可惜,彩叶并没有解决这个问题,所以她把问题交给了聪明又有经验的你,希望你来帮她解决这个问题。
为了方便你解答这个问题,你不需要给出具体的消除过程,只需要输出按原牌堆顺序每张牌分别被放入了哪个栈中。彩叶会帮助你判断你的构造是否正确。
输入格式
第一行包含一个正整数 (),表示卡牌的种类数。
第二行包含 个正整数 (),依次表示初始牌堆从上到下每张牌的点数。保证 中的每种数字恰好出现两次。
保证数据恰好有 组(包括样例),每组数据中的数组 都是从所有的长度为 ,且 中每种数字各出现两次的序列中等概率选择。
输出格式
输出一行,包含 个正整数 ,其中 ,表示初始牌堆中第 张取出的牌被放入了第 个栈中。
如果有多种满足条件的方案,输出任意一种即可。
3
1 2 3 1 3 2
1 1 1 2 2 3
提示
在处理完你的指令后,后 个栈都是空的,而前 个栈分别形如(元素按照从栈底到栈顶的顺序列举):
- ;
- ;
- 。
不难证明存在一种办法消除所有的数。