P1963 [NOI2009] Transformation Sequence

Consider the integers $0, 1, \cdots, N-1$. A transformation sequence $T$ maps $i$ to $T_i$, where $T_i \in \{ 0,1,\cdots, N-1\}$ and $\bigcup_{i=0}^{N-1} \{T_i\} = \{0,1,\cdots , N-1\}$. For all $x, y \in \{0,1,\cdots , N-1\}$, define the distance between $x$ and $y$ as $D(x,y)=\min\{|x-y|,N-|x-y|\}$. Given each $D(i,T_i)$, you need to find a transformation sequence $T$ that satisfies the requirements. If there are multiple valid sequences, output the lexicographically smallest one. Note: For two transformation sequences $S$ and $T$, if there exists $p < N$ such that for $i = 0, 1, \cdots, p-1$, $S_i = T_i$ and $S_p < T_p$, then we say $S$ is lexicographically smaller than $T$.

The first line contains a positive integer $N$, the length of the sequence. The next line contains $N$ integers $D_i$, where $D_i$ denotes the distance between $i$ and $T_i$.

If at least one valid transformation sequence $T$ exists, output one line with $N$ integers, which is the lexicographically smallest $T$ you computed; otherwise output `No Answer`. Note that adjacent numbers are separated by a single space, and there is no trailing space at the end of the line.

- For 30% of the testdata: $N \le 50$. - For 60% of the testdata: $N \le 500$. - For 100% of the testdata: $N \le 10^4$. Translated by ChatGPT 5