P10382 "HOI R1" Random Construction Problem

Little $\iiint$ has nothing to do with this annoying construction problem.

A sequence $a$ is called valid if it satisfies the following requirements: - $a_i = -1$ or $a_i \in [1,n]$. - For every $a_i \not= -1$, add a directed edge $a_i \to i$. The graph formed in this way has no cycles. Now you are given an integer $x$ and a sequence $a$, where all elements of $a$ are integers in the range $[-1,n]$. Please replace every position with $a_i = 0$ by some other integer, so that $\sum\limits ^{n} _{i=1} a_i = x$ and $a$ is valid. If no such solution exists, report that there is no solution.

The first line contains two integers $n$ and $x$. The second line contains $n$ integers, representing the sequence $a$. It is guaranteed that $\forall a_i \in [-1,n]$.

If there is no solution, it means you were fooled, so output a string `Rick`. Otherwise output $n$ integers, representing the sequence $a$ after replacing all elements that are $0$.

**This problem uses bundled tests.** | Subtask | Score | $n \le$ | $x \le$ | Special property | | :----------: | :----------: | :----------: | :----------: | :----------: | | #0 | $13$ | $15$ | $225$ | None | | #1 | $24$ | $10^3$ | $10^9$ | None | | #2 | $27$ | $10^5$ | $10^{18}$ | Yes | | #3 | $36$ | $10^5$ | $10^{18}$ | None | *Special property: it is guaranteed that $\forall a_i = 0$. For all testdata, $1 \le n \le 10^5$, $-10^{18} \le x \le 10^{18}$. *** **Special Judge return value table** - `Accepted.` The answer is correct. - `Oops, your answer is wrong. 1` The correct answer has no solution, but the contestant output says there is a solution. - `Oops, your answer is wrong. 2` The contestant’s output has $\sum a_i \not = x$. - `Oops, your answer is wrong. 3` The contestant’s output contains $0$. - `Oops, your answer is wrong. 4` The contestant’s output contains a cycle. - `Oops, your answer is wrong. 5` While filling in the blanks, the contestant modified positions where the input has $a_i \not= 0$. Translated by ChatGPT 5