← 返回题目列表

Codeforces · 149/C

C. 分组

中文机器翻译题面 查看原题

Petya 非常喜欢足球,尤其是当他父母不在家的时候。每天早上他都会来到院子里,聚集他的朋友们,他们玩一整天。他们不时休息一下吃点东西或做一些家务(例如,给花浇水)。

足球比赛的关键是在比赛开始前公平地分组。院子里有n个男孩在踢足球(包括Petya),每个男孩的踢球技术都用一个非负特征ai来表示(它越大,男孩踢得越好)。

设第一队的球员人数为 x,第二队的球员人数为 y,为第一队效力的男生个人编号为 pi,为第二队效力的男生个人编号为 qi。如果满足三个条件,则将 n 个男孩分成两队被认为是公平的:

- 每个男孩只为一支球队效力 (x + y = n)。
- 团队规模相差不超过一 (|x - y| ≤ 1)。
- 两支球队的足球比赛总技能的差异不超过场内最好球员所拥有的技能值的差异。更正式地说:$$\left| \sum_{i=1}^{x} a_{p_i} - \sum_{i=1}^{y} a_{q_i} \right| \leq \max_{i=1}^{n} a_i$$

你的任务是帮助人们公平地分成两队。确保公平地分成两支球队始终存在。

输入

第一行包含唯一的整数 n (2 ≤ n ≤ 105),代表院子里的人数。下一行包含 n 个空格分隔的正整数 ai (1 ≤ ai ≤ 104),第 i 个数字代表第 i 个男孩的演奏技巧。

输出

在第一行打印一个整数 x — 为一线队效力的男孩人数。在第二行打印 x 个整数——为第一队效力的男孩的个人数量。在第三行打印一个整数 y——为第二队效力的男孩人数,在第四行打印 y 个整数——为第二队效力的男孩的个人人数。不要忘记您应该满足所有三个条件:x + y = n,|x - y| ≤1,限制总技能的条件。

如果有多种方法可以解决问题,请打印其中任何一种。

这些男孩按照输入数据中给出的技能顺序从 1 开始编号。您可以按任何顺序打印属于同一团队的男孩的个人编号。

示例

输入 #1

3
1 2 1

输出 #1

2
1 2
1
3

输入 #2

5
2 3 3 1 1

输出 #2

3
4 1 3
2
5 2

注意

让我们考虑第一个示例测试。在那里,我们将第一个和第二个男孩送到第一队,将第三个男孩送到第二队。让我们检查一下公平分配的所有三个条件。满足第一个限制(所有男孩都参加),满足小组规模的第二个限制(|2 - 1| = 1 ≤ 1),满足技能差异的第三个限制((2 + 1)-(1)= 2 ≤ 2)。