DMOPC '20 Contest 4 P5 - Cyclic Cypher

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 1.0s
Memory limit: 16M
Java 32M
Python 64M

Author:
Problem type

You are working as a cryptographer in a post-apocalyptic world. The most common form of information is transmitted in messages with cyclic arrays of size N where each element is either 1 or -1, taking inspiration from the previously failed binary system. To ensure that the message is not corrupted, the receiver of the message uses an identification number K. The message can be verified if the sum of the products of elements in every cyclic subarray of length K is 0. You would like to send a valid message to a recipient with identification number K. Please find any valid message that can be verified, or determine that no such message exists.

Constraints

1 \le K \le N \le 2^{21}

Subtask 1 [5%]

1 \le K \le N \le 2^4

Subtask 2 [15%]

1 \le K \le N \le 2^{11}

Subtask 3 [20%]

If N and K are expressed as 2^a \times x and 2^b \times y respectively where x and y are odd and a and b are integers, then a > b.

Subtask 4 [60%]

No additional constraints.

Input Specification

The first and only line contains 2 integers N and K, as specified in the problem statement.

Output Specification

If it is impossible to create a valid message, output 0. Otherwise output N space-separated integers (either 1 or -1) on a single line, representing the cyclic array.

Note: your output must follow the standard convention of not having any leading or trailing whitespace, and it must end with a new line.

Sample Input

8 3

Sample Output

-1 -1 1 1 -1 1 -1 1

Explanation

The diagram below shows the cyclic array, with the indices labeled below the elements.

The following list shows the product of every cyclic subarray of length K:

The product of elements from index 1 to 3 is 1.
The product of elements from index 2 to 4 is -1.
The product of elements from index 3 to 5 is -1.
The product of elements from index 4 to 6 is -1.
The product of elements from index 5 to 7 is 1.
The product of elements from index 6 to 8 is -1.
The product of elements from index 7 to 1 is 1.
The product of elements from index 8 to 2 is 1.

Summing, we get 1 - 1 - 1 - 1 + 1 - 1 + 1 + 1 = 0, so this message can be verified. Note that this is not the only possible solution, and other verifiable messages will also be accepted.


Comments

There are no comments at the moment.