DMOPC '21 Contest 3 P2 - Weak Data

View as PDF

Submit solution

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

Problem type

You are generating data for the second problem of the DMOPC, which reads as follows:

Given an integer array A of length N (1 \le N \le 10^6) with elements in the range [-10^9, 10^9], output the number of non-empty contiguous subarrays with an even sum.

Just as you were about to wrap up the last batch of cases, you open Discord to see 8 pings from Keenan, who insists that the data is weak unless there is a test case where the expected output is K. As it is only a few hours before the actual contest, there's no time for you to create such a case by hand. Please write a program to find a case satisfying Keenan's requirement, or determine that his requirement is impossible to satisfy (under the given constraints of the problem).


0 \le K \le 10^{18}

Subtask 1 [50%]

0 \le K \le 10^6

Subtask 2 [50%]

No additional constraints.

Input Specification

The first and only line will contain the integer K.

Output Specification

If it is impossible to satisfy Keenan's requirement under the constraints of the problem, output -1.

Otherwise, output N (1 \le N \le 10^6) on the first line, representing the length of the array.

Then, on the second line, output N integers A_i (-10^9 \le A_i \le 10^9), representing an array of length N that satisfies Keenan's requirement.

If there are multiple arrays satisfying Keenan's requirement, output any one of them.

Sample Input 1


Sample Output 1

5 4 9 1 6

Explanation for Sample 1

The subarrays with even sum are: [5, 4, 9], [4], [4, 9, 1], [4, 9, 1, 6], [9, 1], [9, 1, 6], [6].

Sample Input 2


Sample Output 2



There are no comments at the moment.