AIOC Banner

Problem: Papa and Baby Frog

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


Papa and Baby Frog

Time limit: 1 second
Memory limit: 256 MiB

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 hi.

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

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

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.

Subtasks and Constraints

For all subtasks, you are guaranteed that:

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

Input

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

The second line of input contains n integers h1,..., hn, which are the heights of the stones.

Output

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.

Sample Input 1

4 1
4 1 3 2

Sample Output 1

0001

Sample Input 2

7 2
3 1 2 1 2 2 3

Sample Output 2

0101010

Sample Input 3

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

Sample Output 3

0000010001

Explanation

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:

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

In the third example:

Hence, stones 6 and 10 are potential homes.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 15 November 2019,  6:53am AEDT