Yet Another Permutation Problem 2

각 위치에서 $Q_i=N+1-P_i$로 정한다. $P$가 $1$부터 $N$까지의 정수를 한 번씩 포함하므로, $Q$도 이 정수들을 한 번씩 포함한다. 따라서 $Q$는 순열이다.

모든 $i$에 대해 $P_i+Q_i=N+1$이다. 합으로 이루어진 수열은 일정하므로 비감소한다. 이 구성은 문제에서 보장한 답을 직접 제공한다.

서브태스크 1에서는 $P_i=i$이므로 $Q_i=N+1-i$로 정할 수도 있다. 서브태스크 3에서는 이므로 로 정할 수도 있다. 서브태스크 2와 전체 서브태스크에서는 위의 일반적인 구성을 사용한다.

각 서브태스크의 시간 복잡도는 $O(T+\sum N)$이다. 입력과 출력을 차례로 처리하면 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT5