← 返回题目列表

Codeforces · 982/B

B. 人物巴士

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

角色巴士中有 $$$n$$$ 排座位,每排有 $$$2$$$ 个座位。第 $$$i$$$ 排的两个座位的宽度均为 $$$w_i$$$ 厘米。所有整数 $$$w_i$$$ 都是不同的。

最初巴士是空的。每个 $$$2n$$$ 站都有一名乘客上车。乘客有两种类型:

- 内向的人总是选择两个座位都空的一排。在这些排中,他选择座位宽度最小的一排,并占据其中的一个座位;
- 外向的人总是选择恰好有一个座位(被内向的人占据)的那排。在这些排中,他选择座位宽度最大的一排并占据其中的空位。

您将获得每排座位的宽度以及乘客上车的顺序。确定每位乘客将乘坐哪排。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$) — 总线中的行数。

第二行包含整数序列 $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 10^{9}$$$),其中 $$$w_i$$$ 是第 $$$i$$$ 行中每个座位的宽度。保证所有 $$$w_i$$$ 都是不同的。

第三行包含一个长度为$$$2n$$$的字符串,由数字“0”和“1”组成——描述乘客上车的顺序。如果第 $$$j$$$ 个字符为“0”,则在第 $$$j$$$ 个车站上车的乘客是内向者。如果第 $$$j$$$ 个字符为“1”,则在第 $$$j$$$ 个车站上车的乘客是外向的。保证外向者的数量等于内向者的数量(即两个数字都等于 $$$n$$$),并且对于每个外向者总是有一个合适的行。

输出

打印 $$$2n$$$ 整数 — 乘客将乘坐的行数。乘客的顺序应与输入时的顺序相同。

示例

输入 #1

2
3 1
0011

输出 #1

2 1 1 2

输入 #2

6
10 8 9 11 13 5
010010011101

输出 #2

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

注意

在第一个示例中,第一位乘客(性格内向)选择 $$$2$$$ 行,因为它的座位宽度最小。第二位乘客(性格内向)选择 $$$1$$$ 行,因为它是现在唯一的空行。第三位乘客(性格外向)选择$$$1$$$这一排,因为它只有一个座位,而且座位宽度是该排中最大的。第四位乘客(外向)选择 $$$2$$$ 行,因为它是唯一有空位的行。