{"problem":{"name":"B. Bus of Characters","description":{"content":"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 empt","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF982B"},"statements":[{"statement_type":"Markdown","content":"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.\n\nInitially the bus is empty. On each of $2n$ stops one passenger enters the bus. There are two types of passengers:\n\n*   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;\n*   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.\n\nYou are given the seats width in each row and the order the passengers enter the bus. Determine which row each passenger will take.\n\n## Input\n\nThe first line contains a single integer $n$ ($1 \\le n \\le 200\\,000$) — the number of rows in the bus.\n\nThe 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**.\n\nThe 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.\n\n## Output\n\nPrint $2n$ integers — the rows the passengers will take. The order of passengers should be the same as in input.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在一辆有 $n$ 排座位的公交车上，每排有 $2$ 个座位。第 $i$ 排两个座位的宽度均为 $w_i$ 厘米。所有整数 $w_i$ 互不相同。\n\n初始时公交车为空。在 $2n$ 个站点中，每个站点有一名乘客上车。乘客分为两种类型：\n\n给你每排座位的宽度以及乘客上车的顺序。请确定每位乘客将选择哪一排座位。\n\n第一行包含一个整数 $n$（$1 lt.eq n lt.eq 200 thin 000$）——公交车的排数。\n\n第二行包含序列 $w_1, w_2, dots.h, w_n$（$1 lt.eq w_i lt.eq 10^9$），其中 $w_i$ 表示第 $i$ 排每个座位的宽度。保证所有 $w_i$ 互不相同。\n\n第三行包含一个长度为 $2n$ 的字符串，由数字 '_0_' 和 '_1_' 组成——描述乘客上车的顺序。如果第 $j$ 个字符是 '_0_'，则在第 $j$ 个站点上车的乘客是内向者；如果第 $j$ 个字符是 '_1_'，则在第 $j$ 个站点上车的乘客是外向者。保证外向者人数等于内向者人数（即两者均为 $n$），且对每个外向者都存在合适的排。\n\n请输出 $2n$ 个整数——每位乘客选择的排号。输出顺序应与输入顺序一致。\n\n在第一个例子中，第一位乘客（内向者）选择第 $2$ 排，因为该排座位宽度最小。第二位乘客（内向者）选择第 $1$ 排，因为此时这是唯一空着的排。第三位乘客（外向者）选择第 $1$ 排，因为该排恰好有一个被占用的座位，且其座位宽度是所有此类排中最大的。第四位乘客（外向者）选择第 $2$ 排，因为这是唯一还有空位的排。\n\n## Input\n\n第一行包含一个整数 $n$（$1 lt.eq n lt.eq 200 thin 000$）——公交车的排数。第二行包含序列 $w_1, w_2, dots.h, w_n$（$1 lt.eq w_i lt.eq 10^9$），其中 $w_i$ 表示第 $i$ 排每个座位的宽度。保证所有 $w_i$ 互不相同。第三行包含一个长度为 $2n$ 的字符串，由数字 '_0_' 和 '_1_' 组成——描述乘客上车的顺序。如果第 $j$ 个字符是 '_0_'，则在第 $j$ 个站点上车的乘客是内向者；如果第 $j$ 个字符是 '_1_'，则在第 $j$ 个站点上车的乘客是外向者。保证外向者人数等于内向者人数（即两者均为 $n$），且对每个外向者都存在合适的排。\n\n## Output\n\n请输出 $2n$ 个整数——每位乘客选择的排号。输出顺序应与输入顺序一致。\n\n[samples]\n\n## Note\n\n在第一个例子中，第一位乘客（内向者）选择第 $2$ 排，因为该排座位宽度最小。第二位乘客（内向者）选择第 $1$ 排，因为此时这是唯一空着的排。第三位乘客（外向者）选择第 $1$ 排，因为该排恰好有一个被占用的座位，且其座位宽度是所有此类排中最大的。第四位乘客（外向者）选择第 $2$ 排，因为这是唯一还有空位的排。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of rows.  \nLet $ W = (w_1, w_2, \\dots, w_n) $ be a sequence of distinct positive integers, where $ w_i $ is the width of both seats in row $ i $.  \nLet $ P = (p_1, p_2, \\dots, p_{2n}) \\in \\{0,1\\}^{2n} $ be the sequence of passenger types, where $ p_j = 0 $ denotes an introvert and $ p_j = 1 $ denotes an extrovert.  \nLet $ R_j \\in \\{1, 2, \\dots, n\\} $ be the row assigned to the $ j $-th passenger.  \n\nLet $ S_i \\subseteq \\{ \\text{left}, \\text{right} \\} $ denote the occupancy state of row $ i $, initially $ S_i = \\emptyset $.  \nLet $ O = \\{ i \\in \\{1, \\dots, n\\} \\mid |S_i| = 0 \\} $ be the set of completely empty rows.  \nLet $ H = \\{ i \\in \\{1, \\dots, n\\} \\mid |S_i| = 1 \\} $ be the set of half-occupied rows.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200{,}000 $  \n2. $ 1 \\leq w_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $, and $ w_i \\ne w_j $ for $ i \\ne j $  \n3. $ \\sum_{j=1}^{2n} \\mathbf{1}_{p_j = 0} = n $, $ \\sum_{j=1}^{2n} \\mathbf{1}_{p_j = 1} = n $  \n4. For every extrovert (i.e., $ p_j = 1 $), $ H \\ne \\emptyset $ at the time of boarding.  \n\n**Objective**  \nFor each $ j \\in \\{1, \\dots, 2n\\} $:  \n- If $ p_j = 0 $ (introvert):  \n  Assign $ R_j = \\arg\\min_{i \\in O} w_i $, then update $ S_{R_j} = \\{ \\text{left} \\} $, and remove $ R_j $ from $ O $, add to $ H $.  \n- If $ p_j = 1 $ (extrovert):  \n  Assign $ R_j = \\arg\\max_{i \\in H} w_i $, then update $ S_{R_j} = \\{ \\text{left}, \\text{right} \\} $, and remove $ R_j $ from $ H $.  \n\nOutput the sequence $ (R_1, R_2, \\dots, R_{2n}) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF982B","tags":["data structures","greedy","implementation"],"sample_group":[["2\n3 1\n0011","2 1 1 2"],["6\n10 8 9 11 13 5\n010010011101","6 6 2 3 3 1 4 4 1 2 5 5"]],"created_at":"2026-03-03 11:00:39"}}