33OJ
登录 注册

#P17505. [ICPC 2026 Wuhan I] Iroha and the Kingdom of Construction

    ID: 20233 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 显示难度NOI/NOI+/CTS 上传者: 标签>Special Judge期望分块ICPC2026Dilworth 定理省赛/邀请赛湖北

[ICPC 2026 Wuhan I] Iroha and the Kingdom of Construction

题目描述

兜兜转转,彩叶来到了月读空间里的一个神秘地界 — 构造王国。

听闻你曾经来过此处,彩叶非常开心,并向你分享了她在构造王国中一段有趣的记忆。

构造王国中有一副神奇的纸牌,它有恰好 nn 种不同点数(依次用 11 到 nn 之间的整数表示),每种点数恰好有两张。经过均匀洗牌,这 2n2n 张纸牌构成了一幅牌堆。换句话说:输入数据保证,牌堆是由所有包含 nn 种点数、每种恰好两张牌的合法牌堆中等概率随机生成的。

在这个空间中,彩叶被赋予了一个很强大的能力:生成栈。由于这项能力十分消耗体力,彩叶只能生成 260260 个栈。

现在,彩叶需要按照从上到下的顺序依次取出初始牌堆中的牌。对于每张被取出的牌,彩叶可以将其放入任意一个栈中。

当所有的 2n2n 张牌都放置完毕后,彩叶的栈需要满足以下条件:可以进行若干次如下的 “消除操作”,直到所有牌均被消除完毕:

  • 每次操作选择两个不同的栈,若这两个栈当前的栈顶卡牌点数相同,则将这两张牌同时弹出(删除)。

很可惜,彩叶并没有解决这个问题,所以她把问题交给了聪明又有经验的你,希望你来帮她解决这个问题。

为了方便你解答这个问题,你不需要给出具体的消除过程,只需要输出按原牌堆顺序每张牌分别被放入了哪个栈中。彩叶会帮助你判断你的构造是否正确。

输入格式

第一行包含一个正整数 nn(1≤n≤5×1051 \le n \le 5\times10^5),表示卡牌的种类数。

第二行包含 2n2n 个正整数 a1,a2,…,a2na_1,a_2,\ldots,a_{2n}(1≤ai≤n1 \le a_i \le n),依次表示初始牌堆从上到下每张牌的点数。保证 {1,2,…,n}\{1,2,\ldots,n\} 中的每种数字恰好出现两次。

保证数据恰好有 5050 组(包括样例),每组数据中的数组 aa 都是从所有的长度为 2n2n,且 {1,2,…,n}\{1,2,\ldots,n\} 中每种数字各出现两次的序列中等概率选择。

输出格式

输出一行,包含 2n2n 个正整数 c1,c2,…,c2nc_1,c_2,\ldots,c_{2n},其中 1≤ci≤2601 \le c_i \le 260,表示初始牌堆中第 ii 张取出的牌被放入了第 cic_i 个栈中。

如果有多种满足条件的方案,输出任意一种即可。

3
1 2 3 1 3 2
1 1 1 2 2 3

提示

在处理完你的指令后,后 257257 个栈都是空的,而前 33 个栈分别形如(元素按照从栈底到栈顶的顺序列举):

  1. [1,2,3][1,2,3];
  2. [1,2][1,2];
  3. [3][3]。

不难证明存在一种办法消除所有的数。