NOI '09 P1 - Transformed Sequence

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type
National Olympiad in Informatics, China, 2009

For N integers 0, 1, \dots, N-1, a transformed sequence T can change i to T_i, where T_i \in \{0, 1, \dots, N-1\} and \bigcup_{i=0}^{N-1} \{T_i\} =\{0, 1, \dots, N-1\}. \forall x,y \in \{0, 1, \dots, N-1\}, define the distance between x and y to be D(x, y) = \min\{|x-y|, N-|x-y|\}. Given the distance D(i, T_i) between each i and T_i, you must determine a transformed sequence T that satisfies the requirements. If many sequences satisfy the requirements, then output the lexicographically smallest one.

Note: For two transformed sequences S and T, if there exists a p < N that satisfies S_i = T_i and S_p < T_p for i = 0, 1, \dots, p-1, then we say that S is lexicographically smaller than T.

Input Specification

The first line of input contains a single integer N, the length of the sequence. The following line contains N integers D_i, where D_i is the distance between i and T_i.

Output Specification

If there exists at least one transformed sequence T, then output one line containing N integers, representing the lexicographically smallest transformed sequence T. Otherwise, output No Answer.

Note: Pairs of adjacent numbers in the output must be separated by a single space, and there cannot be trailing spaces.

Sample Input

1 1 2 2 1

Sample Output

1 2 4 0 3


For 20% of the test data, N \le 50.
For 60% of the test data, N \le 500.
For 100% of the test data, N \le 10\,000.

Problem translated to English by Alex.


There are no comments at the moment.