#P7230. [2023省队模拟]宝石装箱

    ID: 7064 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2200提高+/省选-欧拉回路Hierholzer 算法奇偶性分析

[2023省队模拟]宝石装箱

题目描述

有 4n4n 颗宝石,价值分别为 1,2,…,4n1,2,\ldots,4n。宝石共有 nn 种颜色,每种颜色恰好有 44 颗。

请把全部宝石装进两个箱子,使得两个箱子的宝石总价值相等,且每个箱子对每种颜色恰好装入 22 颗宝石。数据保证存在符合条件的划分。

输入格式

第一行一个整数 nn。

接下来 4n4n 个整数 c1,c2,…,c4nc_1,c_2,\ldots,c_{4n},其中 cic_i 表示价值为 ii 的宝石的颜色。每种颜色恰好出现 44 次。

输出格式

输出一行 2n2n 个整数,表示放入第一个箱子的各颗宝石的价值。若有多个方案,输出任意一种即可。

样例输入 1

1
1 1 1 1

样例输出 1

1 4

样例输入 2

2
2 1 1 1 2 2 2 1

样例输出 2

1 2 7 8

样例输入 3

2
1 1 1 2 2 2 2 1

样例输出 3

1 4 5 8

样例 4 见原附加样例文件。

数据范围与约定

对于所有数据,1≤n≤2×1051\le n\le2\times10^5,1≤ci≤n1\le c_i\le n。每个子任务捆绑测试。

子任务 数据范围 分值
1 n≤6n\le6 20
2 n≤100n\le100
3 n≤3000n\le3000
4 n≤2×105n\le2\times10^5 40