409175: GYM103449 C Find Set

After creating $$$10^6$$$ boring problems , Le GrandPaPà decided to create a new one.

Your friend from Strehaia , Le GrandPaPà , once had a set $$$A$$$ of $$$N$$$ positive integers , but had unfortunately lost it. He only knows some properties of the array : It certainly contained $$$K$$$ pairs $$$(i,j)$$$ $$$1 \le i < j \le \lfloor \frac{N}{2} \rfloor$$$ satisfying the following property : $$$$$$A_{i+j} + A_{j-i} = \lfloor \frac{A_{2i} + A_{2j}}{2} \rfloor$$$$$$ Where $$$\lfloor X \rfloor$$$ denotes the biggest integer smaller or equal to $$$X$$$. GrandPaPà gives you integers $$$N,K$$$ and the $$$K$$$ pairs and asks you to find a set that could have been the one he lost.

The input consits of integers $$$N,K$$$ , followed by $$$K$$$ lines denoting the pairs $$$(i,j)$$$. $$$N,K \le 1000$$$

The output consists of $$$N$$$ integers , a set that could be the one GrandPaPà lost. All printed integers must be in range $$$[0,10^9]$$$ , and all must be distinct. Print -1 if there is no solution.

This problem allows partial scoring.

Let T be the number of pairs that satisfy the propriety. The score is given by the following formula :

• 0 points if $$$T < \lfloor \sqrt{K} \rfloor$$$
• $$$\frac{T}{K} \cdot 100$$$ percent of the test score

4 1
1 2

7 4 1 12

The output is correct since $$$A_{1+2} + A_{2-1} = \lfloor \frac{A_{1 \cdot 2} + A_{2 \cdot 2}}{2} \rfloor$$$ $$$\Leftrightarrow$$$ $$$A_3 + A_1 = \lfloor \frac{A_2 + A_4}{2} \rfloor$$$ $$$\Leftrightarrow$$$ $$$1+7 = \lfloor \frac{16}{2} \rfloor$$$ $$$\Leftrightarrow$$$ $$$8 = 8$$$ which is true.

You can find information about Strehaia $$$\href{https://en.wikipedia.org/wiki/Strehaia}{here}$$$