Bus of Characters

题意翻译

# 题目描述 在一辆公交车中有 $n$ 排座位，每一排有两个座位。第 $i$ 排的两个座位的宽度均为 $w_i$ 。所有的 $w_i$ 互不相同。 初始时，公交车是空的。接下来会依次停靠 $2n$ 个站，每一站将上来一名乘客。乘客分为两类： - 内向者：此类乘客总是会选择两个座位都是空的那一排就坐，如果有多排都是空的，他将会选择 $w_i$ 最小的那一排中任意一个空座坐下。 - 外向者：此类乘客总是会选择已有一人就坐（当然是内向者）的那一排，如果有多排都满足条件，他会选择 $w_i$ 最大的那一排的空座坐下。 现在给定每一排的宽度 $w_i$ 以及乘客上车的顺序。请确定每一个乘客将会选择哪一排坐下。 # 输入输出格式 ## 输入格式 第一行包括一个整数 $n$ ($1\leqslant n \leqslant 200000$)——公交车中座位的排数。 第二行为一个序列 $w_1,w_2,\dots,w_n$($1\leqslant w_i \leqslant 10^9$)，其中 $w_i$ 为第 $i$ 排的座位的宽度。保证所有的 $w_i$ 互不相同。 第三行是一个长度为 $2n$ 的01字符串，表示乘客上车的顺序。如果第 $j$ 个字符为'0'，表示第 $j$ 名乘客是内向者，如果第 $j$ 个字符为'1'，表示第 $j$ 名乘客是外向者。**数据保证内向者和外向者人数相同（即均为 $n$ ），对每一名上车的外向者，保证有空座位可以坐。** ## 输出格式 输出 $2n$ 个整数，空格分开，表示每名乘客会选哪一排就座。 # 说明 在第一个样例中： 第1名乘客（内向者）选择了第2排（由于它的宽度最小）。 第2名乘客（内向者）选择了第1排（由于它是唯一的没有人坐的那排）。 第3名乘客（外向者）选择了第1排（由于它正好是有一个人落座，并且宽度最大）。 第4名乘客（外向者）选择了第2排（由于它是唯一的有空座的那排）。

题目描述

In the Bus of Characters there are $ n $ rows of seat, each having $ 2 $ seats. The width of both seats in the $ i $ -th row is $ w_i $ centimeters. All integers $ w_i $ are distinct. Initially the bus is empty. On each of $ 2n $ stops one passenger enters the bus. There are two types of passengers: - an introvert always chooses a row where both seats are empty. Among these rows he chooses the one with the smallest seats width and takes one of the seats in it; - an extrovert always chooses a row where exactly one seat is occupied (by an introvert). Among these rows he chooses the one with the largest seats width and takes the vacant place in it. You are given the seats width in each row and the order the passengers enter the bus. Determine which row each passenger will take.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 200\,000 $ ) — the number of rows in the bus. The second line contains the sequence of integers $ w_1, w_2, \dots, w_n $ ( $ 1 \le w_i \le 10^{9} $ ), where $ w_i $ is the width of each of the seats in the $ i $ -th row. It is guaranteed that all $ w_i $ are distinct. The third line contains a string of length $ 2n $ , consisting of digits '0' and '1' — the description of the order the passengers enter the bus. If the $ j $ -th character is '0', then the passenger that enters the bus on the $ j $ -th stop is an introvert. If the $ j $ -th character is '1', the the passenger that enters the bus on the $ j $ -th stop is an extrovert. It is guaranteed that the number of extroverts equals the number of introverts (i. e. both numbers equal $ n $ ), and for each extrovert there always is a suitable row.

输出格式

Print $ 2n $ integers — the rows the passengers will take. The order of passengers should be the same as in input.

输入输出样例

输入样例 #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 

说明

In the first example the first passenger (introvert) chooses the row $ 2 $ , because it has the seats with smallest width. The second passenger (introvert) chooses the row $ 1 $ , because it is the only empty row now. The third passenger (extrovert) chooses the row $ 1 $ , because it has exactly one occupied seat and the seat width is the largest among such rows. The fourth passenger (extrovert) chooses the row $ 2 $ , because it is the only row with an empty place.