コンテンツにスキップ

DOJ Beginner Contest 9 C - Yet Another Permutation Problem 2

サイト
DOJ
コンテスト
DOJ Beginner Contest 9
問題
C - Yet Another Permutation Problem 2

11 から NN までの整数の順列 PP が与えられます。P1+Q1,P2+Q2,…,PN+QNP_1 + Q_1, P_2 + Q_2, \dots, P_N + Q_N が広義単調増加になるような順列 QQ を 1 つ作る問題です。答えが複数あれば、どれを出力してもかまいません。

テストケースは T≤105T \le 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

Qi=N+1−PiQ_i = N + 1 - P_i とします。

PP が 11 から NN の順列なので、N+1−PiN + 1 - P_i も 11 から NN までを 1 回ずつとり、QQ は順列になります。そして、どの ii でも Pi+Qi=N+1P_i + Q_i = N + 1 です。和がすべて等しいので、広義単調増加の条件を満たします。

Python
for _ in range(int(input())):
N = int(input())
P = list(map(int, input().split()))
print(*[N - p + 1 for p in P])