Problem 6C. 分糖果

题目描述

有 \(n\) 颗糖果，每颗糖果的价值是 \(v_i\)。

现希望将它们分给 \(2\) 名同学，请给出一种 方案 ，最小化：

• 两人获得糖果的总价值之差的绝对值。

我们用长度为 \(n\) 的 01 串来表示方案，\(s_i=0\) 表示第 \(i\) 颗糖果分配给第一名同学，\(s_i=1\) 表示第 \(i\) 颗糖果分配给第二名同学。例如：\(v=\{1,4,7,3\}\) 时，可以将第一枚糖果和第三枚糖果分配给第一名同学，第二枚糖果和第四枚糖果分配给第二名同学。这样，两人获得的总价值之差的绝对值是 \(1\)。对应的方案可以用 \(0101\) 表示。当然，\(0010\)，\(1101\)，\(1010\) 等也是合法的方案。可以证明总价值之差至少是 \(1\)。

如果有多种方案使得两人获得糖果的总价值之差的绝对值都达到最小，输出其中字典序 最小 的方案。对于上面的例子，则要输出 0010。

输入格式

第一行一个整数 \(n\)。

接下来一行 \(n\) 个整数 \(v_i\)，表示糖果的价值。

输出格式

一个长度为 \(n\) 的 01 串，表示方案。注意：需要使得字典序最小。

样例输入1

4
1 4 7 3

样例输出1

0010

样例输入2

5
1 2 1 2 2

样例输出2

00011

数据范围及约定

对于 \(40\%\) 的数据，\(n=2\)。

对于另外 \(20\%\) 的数据，\(\max v_i - \min v_i = 1\)，\(n\) 是偶数。

对于另外 \(20\%\) 的数据，\(n\le 20\)。

以上三部分数据不重合，占本题 \(80\%\) 的分数。

对于 \(100\%\) 的数据，\(2\le n\le 30, 1\le v_i\le 5\times 10^{7}\)。