An Animal Contest 4 P4 - Reindeer Racing

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Python 2.0s
Memory limit: 256M

Problem types

It's the Annual Amazing Christmas season! As part of the reindeers' holiday celebrations, they decide to hold a hurdle race!

There are N reindeer participating in the race, each in their own lane, where lanes are numbered from 1 to N. The track is M metres long, with a hurdle in each lane at every integer metre, that is at metre 1, 2, and so on up to and including M. In this race, there is only one baton, which can only be held by one reindeer at a certain time.

The rules of the race are bizarre. All reindeer start running at the same time, at the exact same speed. However, something odd about the race is that if the reindeer with the baton runs into a hurdle at metre i, the baton flies out of their hoofs and is caught by the reindeer in lane k_i. This only happens after all the reindeer pass this particular hurdle and therefore at most one baton throw occurs at a certain metre i. Strangely, running into a hurdle doesn't affect a reindeer's speed; they continue running in unison with the other competitors.

The winner of the race is the reindeer holding the baton at the end of the race. At the start of the race, the reindeer in a predetermined lane S starts with the baton. As the coach of the reindeer in lane F, you want your reindeer to win, and will resort to anything to achieve your goal.

These reindeer have trained the whole year for this event (yes, reindeer have nothing to do most of the year besides helping Santa deliver presents), and therefore they will never run into a hurdle on their own. However, you, being the coach, plan to secretly throw at least L and at most R bananas during the race, where each banana can be thrown at any lane and at any time during the race, causing the reindeer in that lane to collide into the next hurdle. You need some help to achieve your diabolic plan, so you decide to write a program to output a valid configuration of bananas to be thrown so that the reindeer in lane F wins, or -1 if it is impossible.


1 \le N, M \le 2 \times 10^3

1 \le S, F, k_i \le N

0 \le L \le R \le N \times M

Subtask 1 [40%]

L = 0

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains six space-separated integers N, M, S, F, L, and R.

The next line contains M space-separated integers k_i.

Output Specification

If it is impossible for the reindeer in lane F to end up with the baton at the end of the race, output -1.

Otherwise, first output X, the number of bananas you will throw (L \le X \le R).

Then, output N lines consisting of M integers each, the integer on the i-th line and j-th column being 1 if you threw a banana at the reindeer in lane i to cause them to collide with the j-th hurdle, or 0 if you did not. The number of 1's should equal X.

Note: Any valid output will be accepted.

Sample Input 1

5 10 2 5 0 20
1 2 3 4 5 5 4 3 2 1

Sample Output 1

1 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0 0
0 0 1 0 1 0 0 1 0 1
0 1 0 0 0 0 1 0 1 0
0 0 0 1 0 1 0 0 0 0

Explanation for Sample 1

The reindeer in lane 2 starts with the baton and collides with the hurdle at position 3, handing the baton to the reindeer in lane 3. The reindeer in lane 3 continues with the baton until colliding with the hurdle at position 5, handing the baton to the reindeer in lane 5.

The reindeer in lane 5 collides with hurdle 6, but since k_6 is 5, they simply hand the baton to themselves. The reindeer in lane 5 then continues to the end without hitting any hurdles, becoming the winner.

Sample Input 2

5 5 1 5 22 25
5 4 3 2 1

Sample Output 2


Explanation for Sample 2

Note: You do not need to pass this sample to receive points.

It can be shown that it is impossible for the reindeer in lane 5 to have the baton at the end of the race. Better luck next time!

Sample Input 3

2 2 2 2 0 4
1 1

Sample Output 3

0 0
0 0


There are no comments at the moment.