← 返回题目列表

Codeforces · 2053/B

B. 杰出印象派画家

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

不幸的是,即使在临摹名家画作十年之后,艾瑞克仍然无法成为一名熟练的印象派画家。他想要忘记一些事情,但白熊现象却一直笼罩着他。

Eric 仍然记得整数数组形式的 $$$n$$$ 次展示。他将它们记录为 $$$w_1, w_2, \ldots, w_n$$$。然而,他对印象的记忆力很差。对于每个$$$1 \leq i \leq n$$$,他只能记住$$$l_i \leq w_i \leq r_i$$$。

Eric 认为印象 $$$i$$$ 是唯一的,当且仅当存在一个可能的数组 $$$w_1, w_2, \ldots, w_n$$$ 使得 $$$w_i \neq w_j$$$ 对于所有 $$$1 \leq j \leq n$$$ 和 $$$j \neq i$$$ 成立。

请帮助 Eric 确定印象 $$$i$$$ 对于每个 $$$1 \leq i \leq n$$$ 是否是唯一的,对于每个 $$$i$$$ 是否独立。也许你的判断可以帮助改写最终的故事。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) - 展示次数。

然后是 $$$n$$$ 行,第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 2\cdot n$$$) - $$$w_i$$$ 的最小可能值和最大可能值。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出长度为 $$$n$$$ 的二进制字符串 $$$s$$$:对于每个 $$$1 \leq i \leq n$$$,如果印象 $$$i$$$ 是唯一的,则 $$$s_i=\texttt{1}$$$;否则,$$$s_i=\texttt{0}$$$。不要输出空格。

示例

输入 #1

5
2
1 1
1 1
4
1 3
1 3
1 3
1 3
6
3 6
2 2
1 2
1 1
3 4
2 2
7
3 4
4 4
4 4
1 3
2 5
1 4
2 2
3
4 5
4 4
5 5

输出 #1

00
1111
100110
1001111
011

注意

在第一个测试用例中,唯一可能的数组 $$$w$$$ 是 $$$[1, 1]$$$,使得印象 $$$1$$$ 和 $$$2$$$ 都不唯一(因为 $$$w_1 = w_2$$$)。

在第二个测试用例中,所有印象都可以是唯一的:

- 对于$$$i = 1$$$,我们可以将$$$w$$$设置为$$$[1, 3, 2, 3]$$$,其中$$$w_1 \neq w_2$$$、$$$w_1 \neq w_3$$$和$$$w_1 \neq w_4$$$;
- 对于$$$i = 2$$$,我们可以将$$$w$$$设置为$$$[2, 3, 1, 2]$$$,其中$$$w_2 \neq w_1$$$、$$$w_2 \neq w_3$$$和$$$w_2 \neq w_4$$$;
- 对于 $$$i = 3$$$,我们可以将 $$$w$$$ 设置为 $$$[1, 1, 3, 1]$$$;
- 对于 $$$i = 4$$$,我们可以将 $$$w$$$ 设置为 $$$[2, 3, 3, 1]$$$。

在第三个测试用例中,对于 $$$i = 4$$$,我们可以将 $$$w$$$ 设置为 $$$[3, 2, 2, 1, 3, 2]$$$。因此,印象 $$$4$$$ 是独一无二的。