# B. Like the Bitset [문제 링크](https://codeforces.com/contest/2136/problem/B) ## Problem Statement You must find such a permutation, or determine that no such permutation exists. You are given a binary string $s$ of length $n$, as well as an integer $k$. Aquawave wants to construct a permutation $p$ of length $n$, so that for each $1 \leq i \leq n$, where $s_i = \mathtt{1}$, the following holds: - For each interval $[l, r]$ ($1 \leq l \leq r \leq n$) whose length is at least $k$ (i.e. $r - l + 1 \geq k$), if it covers position $i$ (i.e. $l \leq i \leq r$), then the maximum element among $p_l, p_{l+1}, \ldots, p_r$ is **not** $p_i$. Note that there are **no** such constraints on indices with $s_i = \mathtt{0}$. You have to find such a permutation, or determine that such permutations do not exist. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). The description of the test cases follows. - The first line of each test case contains two integers $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq k \leq n$) — the length of $s$ and the integer in the statements. * The second line contains the binary string $s$ of length $n$ ($s_i = \mathtt{0}$ or $\mathtt{1}$). It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case: - If there is at least one possible permutation: - Print `"YES"` in the first line of output; - Then, print $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$, all $p_i$ are distinct) in the second line — the permutation you constructed. * Otherwise, print `"NO"` in the single line of output. You can output the tokens in any case (upper or lower). For example, the strings `"yEs"`, `"yes"`, `"Yes"`, and `"YES"` will be recognized as positive responses. If there are multiple answers, you may output any of them. ## Footnotes A **binary string** is a string where each character is either $\mathtt{0}$ or $\mathtt{1}$. A **permutation** of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not (since $2$ appears twice), and $[1,3,4]$ is also not a permutation (here $n=3$ but there is a $4$ in the array). ## 풀이 불가능한 경우: k개 이상 '1'이 붙어있는 경우 그렇지 않으면 '0'에 큰수부터 차례로 할당하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int n, k; string s; void solve() { int len=0; for(int i=0;i<n;i++) { if(s[i]=='0') len=0; else len++; if(len>=k) { cout << "NO\n"; return; } } cout << "YES\n"; vector<int> ret(n); int cnt=n; for(int i=0;i<n;i++) { if(s[i]=='0') ret[i] = cnt--; } for(int i=0;i<n;i++) { if(!ret[i]) ret[i] = cnt--; } for(int i=0;i<n;i++) cout << ret[i] << ' '; cout << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { cin >> n >> k >> s; solve(); } } ```