2145B.md (1615B)
1 Source: https://codeforces.com/problemset/problem/2145/B 2 3 B. Deck of Cards 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Monocarp has a deck of cards numbered from $1$ to $n$. Initially, the cards are arranged from smallest to largest, with $1$ on top and $n$ at the bottom. 22 23 Monocarp performed $k$ actions on the deck. Each action was one of three types: 24 25 * remove the top card; 26 * remove the bottom card; 27 * remove either the top or bottom card. 28 29 Your task is to determine the fate of each card: whether it remains in the deck, has been removed, or might be both. 30 31 Input 32 33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 34 35 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$). 36 37 The second line contains a string $s$ of length $k$, consisting of characters 0, 1, and/or {2}. This string describes Monocarp's actions. If the $i$-th character is 0, Monocarp removes the top card on the $i$-th action. If it's 1, he removes the bottom card. If it's 2, either the top or bottom card can be removed. 38 39 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, print a string consisting of $n$ characters. The $i$-th character should be + (plus sign) if the $i$-th card is still in the deck, - (minus sign) if it has been removed, or ? (question mark) if its state is unknown. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 4 2 53 54 01 55 56 3 2 57 58 22 59 60 1 1 61 62 2 63 64 7 5 65 66 01201 67 ``` 68 69 Output 70 71 ``` 72 -++- 73 74 ??? 75 76 - 77 78 --?+?-- 79 ```