Codeforces Solution-B. Bus of Characters-Solution in C, C++, Java, Python

Algorithm

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 $2 n$ 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 $n$ ( $1 \leq n \leq 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 \leq w_{i} \leq 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 $2 n$ , 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.

Output

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

Examples
input
Copy
2
3 1
0011
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 $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.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, p;
pair <int, int> a[N];
string s;
stack <int> st;

int main() {
 	cin >> n;
 	for(int i = 0; i  < n; ++i) {
 		cin >> a[i].first;
 		a[i].second = i + 1;
 	}
 	cin >> s;
 	sort(a, a + n);

 	for(int i = 0; i  < s.length(); ++i)
 		if(s[i] == '0') {
 			cout  < < a[p].second  < < ' ';
 			st.push(a[p].second);
 			++p;
 		} else {
 			cout  < < st.top()  < < ' ';
 			st.pop();
 		}
 	cout  < < endl;

  return 0;
}

Copy The Code & Try With Live Editor

Input

–

cmd

2
3 1
0011

Output

–

cmd

2 1 1 2

Demonstration

Codeforces Solution-B. Bus of Characters-Solution in C, C++, Java, Python,Bus of Characters,Codeforces Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 11 months ago 245 0