codeforces-scrape

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

1659B.md (2386B)


      1 Source: https://codeforces.com/problemset/problem/1659/B
      2 
      3 B. Bit Flipping
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given a binary string of length $n$. You have exactly $k$ moves. In one move, you must select a single bit. The state of all bits except that bit will get flipped ($0$ becomes $1$, $1$ becomes $0$). You need to output the lexicographically largest string that you can get after using all $k$ moves. Also, output the number of times you will select each bit. If there are multiple ways to do this, you may output any of them.
     22 
     23 A binary string $a$ is lexicographically larger than a binary string $b$ of the same length, if and only if the following holds:
     24 
     25 * in the first position where $a$ and $b$ differ, the string $a$ contains a $1$, and the string $b$ contains a $0$.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 1000$)  — the number of test cases.
     30 
     31 Each test case has two lines. The first line has two integers $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$; $0 \leq k \leq 10^9$).
     32 
     33 The second line has a binary string of length $n$, each character is either $0$ or $1$.
     34 
     35 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, output two lines.
     40 
     41 The first line should contain the lexicographically largest string you can obtain.
     42 
     43 The second line should contain $n$ integers $f_1, f_2, \ldots, f_n$, where $f_i$ is the number of times the $i$-th bit is selected. The sum of all the integers must be equal to $k$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 6
     51 
     52 6 3
     53 
     54 100001
     55 
     56 6 4
     57 
     58 100011
     59 
     60 6 0
     61 
     62 000000
     63 
     64 6 1
     65 
     66 111001
     67 
     68 6 11
     69 
     70 101100
     71 
     72 6 12
     73 
     74 001110
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 111110
     81 1 0 0 2 0 0 
     82 111110
     83 0 1 1 1 0 1 
     84 000000
     85 0 0 0 0 0 0 
     86 100110
     87 1 0 0 0 0 0 
     88 111111
     89 1 2 1 3 0 4 
     90 111110
     91 1 1 4 2 0 4
     92 ```
     93 
     94 Note
     95 
     96 Here is the explanation for the first testcase. Each step shows how the binary string changes in a move.
     97 
     98 * Choose bit $1$: $\color{red}{\underline{1}00001} \rightarrow \color{red}{\underline{1}}\color{blue}{11110}$.
     99 * Choose bit $4$: $\color{red}{111\underline{1}10} \rightarrow \color{blue}{000}\color{red}{\underline{1}}\color{blue}{01}$.
    100 * Choose bit $4$: $\color{red}{000\underline{1}01} \rightarrow \color{blue}{111}\color{red}{\underline{1}}\color{blue}{10}$.
    101 
    102 The final string is $111110$ and this is the lexicographically largest string we can get.