← 返回题目列表

Codeforces · 378/B

B. 半决赛

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

跑步赛刚刚进行了两场半决赛。每场半决赛都有n名参赛者。晋级决赛的选手有 n 名,他们的选择如下:每场半决赛中,我们选出 k 名在半决赛中表现最好的人(0 ≤ 2k ≤ n),而决赛的所有其他名额则分配给半决赛中未进入前 k 名但进入其他最好成绩的 n - 2k 名选手。

赛事主办方尚未确定k值,所以参赛者想知道还有谁有机会进入决赛,谁可以回家。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 每场半决赛的参赛人数。

接下来的 n 行每行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ 109)——对应的第 i 名参赛者在第一场和第二场半决赛的成绩(他跑完半决赛距离所需的毫秒数)。所有结果都是不同的。序列 a1, a2, ..., an 和 b1, b2, ..., bn 按升序排序,即按照参赛者在相应半决赛中完成的顺序排序。

输出

打印两个由 n 个字符组成的字符串,每个字符串等于“0”或“1”。第一行应对应第一场半决赛的参赛者,第二行应对应第二场半决赛的参赛者。如果第 j 个半决赛的第 i 个参赛者有机会晋级决赛,则第 j 行中的第 i 个字符应等于“1”,否则应等于“0”。

示例

输入 #1

4
9840 9920
9860 9980
9930 10020
10040 10090

输出 #1

1110
1100

输入 #2

4
9900 9850
9940 9930
10000 10020
10060 10110

输出 #2

1100
1100

注意

考虑第一个样本。每场半决赛有4名参赛者。第一场半决赛的成绩为9840、9860、9930、10040。第二场半决赛的成绩为9920、9980、10020、10090。

- 如果k = 0,则仅根据时间确定决赛入围者,因此玩家9840、9860、9920和9930晋级决赛。
- 如果k = 1,则两场半决赛的获胜者进入决赛(成绩分别为9840和9920),其他名次由时间决定(这些名额由跑完距离为9860和9930毫秒的运动员获得)。
- 如果 k = 2,则第一名和第二名从每个半决赛中晋级,这些是结果为 9840、9860、9920 和 9980 毫秒的参与者。