CF149C Division into Teams

Petya 非常喜欢足球，尤其是当父母不在家的时候。每天早上，他都会来到院子里，召集他的朋友们，然后大家一起踢一整天的球。偶尔他们会停下来吃点东西，或者做些杂事（比如浇花）。 足球比赛中，最关键的是在比赛开始前公平地分组。有 $n$ 个男孩在院子里踢球（包括 Petya 本人），每个男孩踢球的水平用一个非负数 $a_{i}$ 表示（数值越大，水平越高）。 我们记第一队的人数为 $x$，第二队的人数为 $y$，分别用 $p_{i}$ 和 $q_{i}$ 表示属于第一队和第二队的男孩编号。将 $n$ 个男孩分成两队被认为是公平的，当且仅当满足以下三个条件： - 每个男孩恰好只属于一支队伍（即 $x+y=n$）。 - 两队人数相差不超过 1（即 $|x-y|\leq 1$）。 - 两队的总水平分差不超过院子里水平最高的男孩的水平值。更形式化地表示： $$ |\sum_{i=1}^{x} a_{p_{i}} - \sum_{i=1}^{y} a_{q_{i}}| \le \max\limits_{i=1..n} a_i $$ 你的任务是帮助这些男孩公平地分成两队。题目保证每组数据都存在一种公平分组方案。

第一行包含一个整数 $n$（$2\leq n\leq 10^{5}$），表示院子里的男孩数。第二行包含 $n$ 个正整数 $a_{i}$（$1\leq a_{i}\leq 10^{4}$），第 $i$ 个数表示第 $i$ 个男孩的踢球水平。

第一行输出一个整数 $x$，表示分在第一队的男孩人数。 第二行输出 $x$ 个整数，表示第一队每个男孩的编号。 第三行输出一个整数 $y$，表示分在第二队的男孩人数。 第四行输出 $y$ 个整数，表示第二队每个男孩的编号。 需要满足 $x+y=n$、$|x-y|\leq 1$ 以及总水平分差的公平性要求。 如果存在多种分法，输出任意一种即可。 男孩的编号按照输入顺序从 1 到 $n$ 编号。每支队伍内的编号输出顺序不限。

让我们考虑第一个样例测试。在这里，我们将第一个和第二个男孩分到第一队，将第三个男孩分到第二队。检查公平分组的三个条件：第一个条件满足（所有人都参与），第二个条件满足（$|2-1|=1\leq 1$），第三个条件也满足（$(2+1)-(1)=2\leq 2$）。 由 ChatGPT 5 翻译