seuOJ475 - 划分(sequence version)

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：迎新赛, 2023

题目描述

DingDing 有一个长度为 $n$ 的序列，你需要把这个序列划分成两个部分，使得每个数字属于且仅属于一个部分。定义一个部分的权值为该部分中最小的两个数字的和，你需要使两个部分权值中的较小值尽可能大，如果一个部分中没有数字或者只有一个数字，那么该部分的权值为 $+\infty$（正无穷）。

输入格式

第一行，一个数字 $t(1\le t\le 10^4)$，代表数据组数。

对于每组数据：
第一行，一个整数 $n(2\le n \le 2·10^5)$，代表序列长度。
接下来一行共 $n$ 个数字，代表这个序列 $a$，其中 $1\le a_i\le 10^9$。

保证同一测试点内的 $\sum n \le 2·10^5$。

输出格式

对于每组数据，输出一行长度为 $n$ 的字符串，字符串应只由字符 $0,1$ 组成，代表每个数字被划分到哪个集合。

如果有多种最优的划分方法，输出任何一种都是正确的。

样例

输入样例

3
6
4 6 3 100 5 1
4
1 1 1 1
5
1 2 3 4 5

输出样例

000101
0000
01110

提示
在样例的第 $1$ 组数据中，第 $1$ 个部分为 $[4,6,3,5]$，第 $2$ 个部分为 $[100,1]$，两部分的权值分别为 $7$ 和 $101$。因为 $\min(7,101)=7$，所以两个部分权值的最小值为 $7$。
在样例的第 $2$ 组数据中，第 $1$ 个部分为 $[1,1,1,1]$，第 $2$ 个部分为 $[]$，两部分的权值分别为 $2$ 和 $+\infty$。因为 $\min(2,{+\infty})=2$，所以两个部分权值的最小值为 $2$。此外，在第 $2$ 组数据中，输出任何长度为 $4$、只由字符 $0,1$ 构成的字符串都是正确的。