codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```