V-Sort

수열의 각 위치를 정점으로 보고, 한 번에 교환할 수 있는 두 위치 사이에 무향 간선을 놓는다. 같은 연결 컴포넌트 안에서는 경로의 간선 교환을 반복하여 임의의 재배열을 할 수 있다. 따라서 각 컴포넌트의 현재 값의 멀티셋과 목표 값의 멀티셋이 같으면, 그리고 그때만 정렬이 가능하다. 위치 $A_i,B_i$의 목표 값은 모두 $i$이다.

• 서브태스크 1 ($X=Y=0$): 교환 가능한 위치는 $A_i,B_i$뿐이다. 두 위치의 목표 값이 모두 이므로 처음부터 모든 여야 한다. 시간에 확인한다.

$X=N$ 또는 $Y=N$이면 해당 종류의 간선은 없다. 고립된 위치도 검사해야 하며, 중복 원소가 허용되므로 값의 합만 비교해서는 안 된다. 전체 풀이의 총 시간은 $O(\sum N)$이다. 모든 인덱스와 빈도의 절댓값은 $1\,000\,000$ 이하이므로 64비트 정수 범위를 넘는 연산은 필요하지 않다.

Solution written by GPT