#P11612. [2020年省队模拟]排列

    ID: 10760 传统题 2000ms 512MiB 尝试: 4 已通过: 2 难度: 6 上传者: 标签>贪心动态规划CF2100构造排序堆模拟DFS

[2020年省队模拟]排列

Problem B. 排列

输入:标准输入 输出:标准输出 时间限制: 2 秒内存限制: 512 MB

小 G 的班上有n×(n+1)n\times (n+1) 位同学。体育课上,他们从左至右站成一排。因为没有两人一样高,所以小 G 在心中将他们从矮到高排了序。按照从左至右站好的顺序,她用一个 11 至n×(n+1)n\times (n+1) 的排列pp 表示出了他们的相对身高。其中pip_{i} 越大即代表第ii 名同学越高。

体育老师想要保留2n2n 位同学,并将其余n×(n−1)n\times (n-1) 名同学移走。他希望这2n2n 位同学中最高的和次高的相邻、第33 高的和第44高的相邻⋯⋯第2n−12n-1 高的和第2n2n 高的(即次矮和最矮)相邻。这2n2n 名同学的相对位置不可改变。

小 G 证明了这样的方案一定存在。现在请你给出一种合法的方案,如有多种可输出任意一种。

输入格式

第一行,一个正整数nn

第二行,n×(n+1)n\times (n+1) 个正整数,表示排列pp

建议使用 scanf 或其他快速读入方式

输出格式

一行,2n2n 个正整数,表示选出的2n2n 名同学的位置(从左至右、从 11 开始编号)。你必须保证这 2n2n 个数是在 [1,n×(n+1)][1,n\times (n+1)] 内互不相同的,并且从小到大排好序。

样例 1

样例输入

3
9 7 10 4 8 5 12 11 1 3 2 6

样例输出

3 5 7 8 9 11

样例解释 1

选出的 66 个人身高为:10,8,12,11,1,210,8,12,11,1,2,容易验证其合法性。事实上这组样例中共有 101101 个合法的方案,输出任意一种皆可。

数据范围

对 3030% 的数据,n≤4n\le 4

对 6060% 的数据,n≤70n\le 70

对另外 1010% 的数据,保证身高从左至右有序(即p1<p2<...<pn(n+1)p_{1}<p_{2}<...<p_{n(n+1)} 或p1>p2>...>p_{1}>p_{2}>...> pn(n+1)p_{n(n+1)})

对 100100% 的数据,1≤n≤10001\le n\le 1000