An Animal Contest 4 P1 - Dasher's Digits - DMOJ: Modern Online Judge

An Animal Contest 4 P1 - Dasher's Digits

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

Dasher the reindeer has a string $X$ $X$ with $N$ $N$ characters, where $M$ $M$ characters are 0's and the rest are uppercase Latin letters. Each 0 is assigned a "cheer value" $a_i$ $a_{i}$ . The cheer values are $a_1, a_2, \dots, a_M$ $a_{1}, a_{2}, \dots, a_{M}$ where $a_1$ $a_{1}$ corresponds to the cheer value for the first 0 in $X$ $X$ , $a_2$ $a_{2}$ the cheer value for the second 0, and so on.

Dasher wants to get rid of all the 0's in his string, so he performs the following algorithm while there are still 0's present:

If the frontmost character is 0, subtract that 0's cheer value by $1$ $1$ . If this cheer value becomes $0$ $0$ , remove this 0. Otherwise, move it, along with its cheer value, to the back of the string.
Otherwise, take the frontmost character and move it to the back of the string.

For strings that are extensive in length, performing the algorithm manually is a tedious process. Dasher requires your assistance to output the string after all 0's have been removed through the usage of the mentioned algorithm.

Constraints

$2 \le N \le 10^6$ $2 \leq N \leq 10^{6}$

$1 \le M < N$ $1 \leq M < N$

$1 \le a_i \le 10^9$ $1 \leq a_{i} \leq 10^{9}$

$X$ $X$ contains at least one non-0 character.

Subtask 1 [20%]

$M = 1$ $M = 1$

Subtask 2 [30%]

$M \le 2$ $M \leq 2$

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line will contain two space-separated integers $N$ $N$ and $M$ $M$ .

The second line will contain $X$ $X$ , which has at least one non-0 character, and may contain leading 0's.

The next line will contain $M$ $M$ space-separated integers $a_i$ $a_{i}$ .

Output Specification

Output the string $X$ $X$ after all 0's are removed with the algorithm described.

Sample Input

Copy

7 1
US0AMOG
2

Sample Output

Copy

AMOGUS

Explanation

The following shows the results of performing the algorithm manually to obtain our answer:

US0AMOG → S0AMOGU → 0AMOGUS → AMOGUS0 → MOGUS0A → OGUS0AM → GUS0AMO → US0AMOG → S0AMOGU → 0AMOGUS → AMOGUS

Comments

1

jfan27 commented on May 14, 2024, 11:57 a.m.

Bro why am I getting tle on a linear time solution

1

Viv_CCGS commented on May 15, 2024, 11:29 a.m.

6 1

UGH0RO

1

5

Aetheryx_George commented on Feb. 16, 2022, 4:48 a.m.

AMONGUS SUS

44

thomas_li commented on Jan. 3, 2022, 3:17 a.m. ← edited →