解説 · 582

解説

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

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

Solution written by GPT5

解説

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

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

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

Solution written by GPT5