Continuous 1

AtCoder

IDarc150_a

Time2000ms

Memory256MB

Difficulty—

You are given a string of length $N$, $S=S_1S_2\dots S_N$, consisting of `0`, `1`, and `?`. We like to replace every `?` with `0` or `1` so that all of the following conditions are satisfied. * $S$ contains exactly $K$ occurrences of `1`. * These $K$ occurrences of `1` are consecutive. That is, there is an $i\ (1 \leq i \le N-K+1)$ such that $S_i=S_{i+1}=\dots=S_{i+K-1}=$ `1`. Determine whether there is exactly one way to replace the characters to satisfy the conditions. You have $T$ test cases to solve. ## Constraints * $1 \leq T \leq 10^5$ * $1 \leq K < N \leq 3 \times 10^5$ * $S$ is a string of length $N$ consisting of `0`, `1`, and `?`. * The sum of $N$ across the test cases is at most $3 \times 10^5$. ## Input The input is given from Standard Input in the following format: $T$ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_T$ Each case is in the following format: $N$ $K$ $S$ [samples]

Samples

Input #1

4
3 2
1??
4 2
?1?0
6 3
011?1?
10 5
00?1???10?

Output #1

Yes
No
No
Yes

For the first test case, turning $S$ into `101`, for instance, does not satisfy the conditions since the `1`s will not be consecutive. The only way to satisfy the conditions is to turn $S$ into `110`.
For the second test case, we may turn $S$ into `1100` or `0110` to satisfy the conditions, so there are two ways to satisfy them.
For the third test case, there is no way to replace the characters to satisfy the conditions.

API Response (JSON)

{
  "problem": {
    "name": "Continuous 1",
    "description": {
      "content": "You are given a string of length $N$, $S=S_1S_2\\dots S_N$, consisting of `0`, `1`, and `?`. We like to replace every `?` with `0` or `1` so that all of the following conditions are satisfied. *   $S$",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc150_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string of length $N$, $S=S_1S_2\\dots S_N$, consisting of `0`, `1`, and `?`.\nWe like to replace every `?` with `0` or `1` so that all of the following conditions are satisfied.\n\n*   $S$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments