Codeforces Round #484 (Div. 2) B. Bus of Characters（STL+贪心）982B

原博主：https://blog.csdn.net/amovement/article/details/80358962

B. Bus of Characters

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

In the Bus of Characters there are nn rows of seat, each having 22 seats. The width of both seats in the ii-th row is wiwi centimeters. All integers wiwi are distinct.

Initially the bus is empty. On each of 2n2n 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.

Input

The first line contains a single integer nn (1≤n≤2000001≤n≤200000) — the number of rows in the bus.

The second line contains the sequence of integers w1,w2,…,wnw1,w2,…,wn (1≤wi≤1091≤wi≤109), where wiwi is the width of each of the seats in the ii-th row. It is guaranteed that all wiwi are distinct.

The third line contains a string of length 2n2n, consisting of digits '0' and '1' — the description of the order the passengers enter the bus. If the jj-th character is '0', then the passenger that enters the bus on the jj-th stop is an introvert. If the jj-th character is '1', the the passenger that enters the bus on the jj-th stop is an extrovert. It is guaranteed that the number of extroverts equals the number of introverts (i. e. both numbers equal nn), and for each extrovert there always is a suitable row.

Output

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

Examples

input

Copy

output

Copy

2 1 1 2

input

Copy

6

10 8 9 11 13 5

010010011101

output

Copy

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

Note

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

一、原题地址

http://codeforces.com/contest/982/problem/B

二、大致题意

一辆公交有n排座位，每排座位有两个椅子。

接着给出每排座位的宽度。

这时有2*n个人要上车，这群人有两种类型。

1、内向的人：会优先选择座位宽度最小的那排就坐，最好旁边是没人的。

2、外向的人：会优先选择座位旁边有人的那排就坐，在此基础上座位选择越大越好。

三、思路

我们可以先把座位的宽度进行排序。

1、当内向的人上车时，我们记录一个pos表示当前内向的人最优的位置，同时将座位的编号存入栈。

2、当外向的人上车时，我们提取栈内最顶端的元素，因为内向的人是按照座位宽度从小到大入座的，所以此时的栈顶元素，必定为有内向的人就坐的宽度最大的位置。同时删除栈顶元素，表示这个位置被使用了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<string>

#include<algorithm>

#include<vector>

#include<queue>

#include<set>

#include<map>

#include<stack>

using namespace std;

const int inf = 0x3f3f3f3f;

long long  gcd(long long  a, long long  b) { return a ==  ? b : gcd(b % a, a); }

int n;

struct SEAT

{

    int w, id;

}seat[];

bool cmp(SEAT xx, SEAT yy)

{

    return xx.w < yy.w;

}

int main()

{

    scanf("%d", &n);

    for (int i = ; i <= n; i++)

    {

        scanf("%d", &seat[i].w);

        seat[i].id = i;

    }

    sort(seat + , seat +  + n, cmp);

    char s[ * ];

    scanf("%s", s);

    int pos0 = ;

    stack<int>sta;

    for (int i = ; i <  * n; i++)

    {

        if (s[i] == '')

        {

            printf("%d ", seat[pos0].id);

            sta.push(seat[pos0].id);

            pos0++;

        }

        else if (s[i] == '')

        {

            printf("%d ", sta.top());

            sta.pop();

        }

    }

    getchar();

    getchar();

}

巴特西

Codeforces Round #484 (Div. 2) B. Bus of Characters（STL+贪心）982B

三、思路

最新文章

热门文章