LCC '21 Contest 6 J3 - Sprinklers

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 128M

Problem type

It's May, and summer is in full swing!

Elen lives on a street of N adjacent houses, all of them being numbered an integer from 1 to N. Being in a suburban neighbourhood, all of these houses have fragrant gardens and a sprinkler system on their front lawn.

On a particularly sweltering day, M of these houses decide to turn on their sprinklers. However, since the sprinklers on Elen's street are interconnected, whenever one house turns on its sprinkler, the sprinklers of that house and adjacent houses will flip states. If one of the three was previously on, it would turn off, and vice versa.

Elen wants to know which houses will have their sprinklers still on by the end of the day.

Input Specification

The first line will contain the integer N and M, the number of houses on Elen's street, and the number of houses that turn on their sprinklers.

The following M lines will contain a single integer h_i, the address of the next house to turn on their sprinkler.

Assume that all houses start with their sprinklers turned off and M of them turn sequentially in the order inputted. Note that if a house's sprinkler was already on and it was the next input, it would flip and turn off.


1 \le N, M \le 5\,000

1 \le h_i \le N

Output Specification

Print the addresses of all houses with their sprinklers on, space-separated on one line in increasing order. It is guaranteed that there will be at least one house with its sprinklers on.

Sample Input

6 3

Sample Output

1 3 5


Let us represent a house with a sprinkler on using X, and a house without a sprinkler on using .. Simulating the moves:

  1. .XXX..
  2. .X..X.
  3. X.X.X.

Therefore, houses 1, 3, and 5 have their sprinklers on at the end of the day.


There are no comments at the moment.