절반 재배열

틀린 위치의 집합을 $M=\{i\mid P_i\ne i\}$라 하고 $m=|M|$이라 하자.

$m=0$이면 답은 $0$이다.

$1\le m\le N$이면 답은 $1$이다. 모든 틀린 위치를 고르고, 부족한 수만큼 고정점을 추가로 고르면 한 번의 재배열만으로 정렬할 수 있다.

이제 $m>N$이라고 하자. 두 번의 재배열에서 고르는 위치 집합을 각각 $A,B$라고 하자. $|A|=|B|=N$이므로

$$|A\cap B|=|\{1,\cdots,2N\}\setminus(A\cup B)|$$

가 성립한다. $A\cup B$ 밖의 위치는 한 번도 선택되지 않으므로 처음부터 고정점이어야 한다.

고정점이 하나 이상 존재하면 답은 $2$이다. $m>N$이므로 한 번으로는 불가능하고, 고정점 하나를 두 재배열에서 모두 선택하지 않는 위치로 두어 항상 두 번 안에 정렬할 수 있다.

이제 고정점이 하나도 없다고 하자. 위 등식에서 $A\cup B$ 밖에는 아무 위치도 있을 수 없으므로 $A\cap B=\varnothing$이고, $A,B$는 전체 위치를 정확히 둘로 나눈다. 첫 번째 재배열에서 선택한 위치는 두 번째 재배열에서 다시 선택되지 않는다. 따라서 첫 번째 재배열만으로 $A$의 모든 위치가 제자리에 와야 한다.

순열을 사이클로 분해하자. 한 사이클의 일부 위치만 $A$에 들어가면, 그 위치들 중 적어도 하나가 필요로 하는 값은 $B$에 남게 된다. 따라서 $A$는 몇 개의 사이클 전체의 합집합이어야 한다. 반대로, 길이의 합이 정확히 $N$인 사이클들을 고를 수 있다면 그 사이클들을 첫 번째 재배열에서, 나머지를 두 번째 재배열에서 각각 정렬할 수 있다.

따라서 고정점이 없는 경우, 두 번으로 정렬할 수 있는 필요충분조건은 사이클 길이들 중 일부의 합이 정확히 $N$인 것이다. 이 조건은 부분합 DP로 $O(N^2)$에 판정할 수 있다.

그러한 부분집합이 존재하면 답은 $2$이고, 존재하지 않으면 답은 $3$이다. 실제로 두 번은 위 필요조건 때문에 불가능하다. 한편 첫 번째 재배열로 임의의 한 위치를 고정점으로 만든 뒤, 고정점이 있는 경우를 적용하면 세 번 안에는 항상 정렬할 수 있다.

따라서 답은 항상 $0,1,2,3$ 중 하나이다. 각 테스트 케이스의 시간 복잡도는 $O(N^2)$이고, 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5.6