Want to try solving this problem? You can submit your code online if you log in or register.

Papa and Baby frog live among a line of *n* **equally-spaced** stones, numbered 1 to *n*, from left to right. Stone *i* has a positive integer height *h*_{i}.

The frogs can jump between stones, and do so, according to the following rules:

A single jump moves Papa frog to the

**closest**stone that has a**strictly greater**height than his current stone. If there are multiple options, he chooses the**rightmost**among these;A single jump moves Baby frog to the

**closest**stone that has a**strictly smaller**height than her current stone. If there are multiple options, she chooses the**rightmost**among these.

Papa frog would like to choose a stone to be *home*, and a **different** stone to be *school*. He requires that:

Papa frog can jump from home to school, in no more than

*k*jumps; andBaby frog can jump from school to home, in no more than

*k*jumps.

A stone is called a *potential home* if there is **at least one** other stone that can be chosen as school, if this stone is chosen as home.

Your task is to help the frogs determine which stones are potential homes.

For all subtasks, you are guaranteed that:

*n*≥ 21 ≤

*k*≤*n*For all stones

*i*, 1 ≤*h*_{i}≤ 1,000,000,000

Additional constraints for each subtask are given below.

Subtask | Points | n |
k |
---|---|---|---|

1 | 10 | n ≤ 2000 |
k = 1 |

2 | 10 | n ≤ 2000 |
k ≤ 5 |

3 | 20 | n ≤ 2000 |
k ≤ 100 |

4 | 20 | n ≤ 2000 |
k ≤ n |

5 | 20 | n ≤ 100,000 |
k ≤ 5 |

6 | 10 | n ≤ 100,000 |
k = n |

7 | 10 | n ≤ 100,000 |
k ≤ n |

The first line of input contains the two integers, *n* and *k*.

The second line of input contains *n* integers *h*_{1},..., *h*_{n}, which are the heights of the stones.

The output should contain a string of *n* characters on a single line. The *i*-th of these characters should be `1`

, if stone *i* is a potential home, or `0`

, otherwise.

```
4 1
4 1 3 2
```

`0001`

```
7 2
3 1 2 1 2 2 3
```

`0101010`

```
10 3
10 5 6 4 7 3 8 2 9 1
```

`0000010001`

In the first example, only stone 4 can be chosen as home, when stone 3 is chosen as school. Hence, stone 4 is the only potential home.

In the second example:

Stone 2 can be chosen as home, when stone 1 is chosen as school. Papa frog jumps through stones 2→3→1, whereas Baby frog jumps directly from stone 1 to stone 2.

Stone 4 can be chosen as home, when stone 5 is chosen as school. Papa and Baby frog both jump directly between home and school, and vice-versa.

Stone 6 can be chosen as home, when stone 7 is chosen as school. Papa and Baby frog both jump directly between home and school, and vice-versa.

Hence, stones 2, 4 and 6 are potential homes.

In the third example:

Stone 6 can be chosen as home, when stone 1 is chosen as school. Papa frog jumps through stones 6→7→9→1, whereas Baby frog jumps through stones 1→2→4→6.

Stone 10 can be chosen as home, when stone 9 is chosen as school. Papa and Baby frog both jump directly between home and school, and vice-versa.

Hence, stones 6 and 10 are potential homes.

Privacy
statement

© Australian Mathematics Trust 2001-2023

Page generated: 21 September 2023, 11:03pm AEST