题目描述

在一辆公交车中有 $n$ 排座位，每一排有两个座位。第i排的两个座位的宽度均为 $w_i$。所有的 $w_i$ 互不相同。

初始时，公交车是空的。接下来会依次停靠 $2n$ 个站，每一站将上来一名乘客。

乘客分为两类：

内向者：此类乘客总是会选择两个座位都是空的那一排就坐，如果有多排都是空的，他将会选择 $w_i$ 最小的那一排中任意一个空座坐下。

外向者：此类乘客总是会选择已有一人就坐（当然是内向者）的那一排，如果有多排都满足条件，他会选择 $w_i$ 最大的那一排的空座坐下。

现在给定每一排的宽度 $w_i$ 以及乘客上车的顺序。请确定每一个乘客将会选择哪一排坐下。

输入格式

第一行包括一个整数 $n (1<=n<=200000)$——公交车中座位的排数。

第二行为一个序列 $w_1,w_2,…,w_n(1<=w_i<=10^9)$，其中 $w_i$ 为第 $n$ 排的座位的宽度。保证所有的 $w_i$ 互不相同。

第三行是一个长度为 $2n$ 的 $01$ 字符串，表示上车顺序。如果第 $j$ 个字符为 0，表示第 $j$ 名乘客是内向者，如果第 $j$ 个字符为 1，表示第 $j$　名乘客是外向者。数据保证内向者和外向者人数相同（即均为 $n$），对每一名上车的外向者，保证有空座位可以坐。

输出格式

输出 $2n$个整数，空格分开，表示每名乘客会选哪一排就座。

#include<bits/stdc++.h>
using namespace std;

int n,top=-1,j,lar[210],num[1000005],temp[450];
struct pas{
	char c;
	int order;
}line[800];


int main()
{
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
		cin>>lar[i];
		num[lar[i]]=i;
	}
	
	for(int i=0;i<2*n;i++) 
	{
		cin>>line[i].c;
	}
	
	sort(lar,lar+n);
	
	for(int i=0;i<2*n;i++)
	{
	    if(line[i].c=='0')
		{
		    temp[++top]=i;
			line[i].order=num[lar[j++]]; 
		}
		else
		{
			line[i].order=line[temp[top]].order;
			top--;
		}
	}
	
	for(int i=0;i<2*n;i++) 
	{
		cout<<line[i].order+1<<' ';
	}
	return 0;
}