중앙값 정렬 timer 40s memory 1024MB

서로 다른 \mathbf{N}개의 항목 x_1, x_2, \dots, x_\mathbf{N}을 정렬하고 싶다. 하지만 불행히도 두 항목을 직접 비교할 방법이 없다. 당신에게 가능한 것은, 세 항목을 주면 그 셋 중에서 중앙값(median), 즉 최솟값도 최댓값도 아닌 항목이 무엇인지 알아내는 것뿐이다.

예를 들어 \mathbf{N} = 5이고 다음을 알고 있다고 하자:

• x_1은 \{x_1, x_2, x_3\}의 중앙값이다.
• x_2은 \{x_2, x_3, x_4\}의 중앙값이다.
• x_3은 \{x_3, x_4, x_5\}의 중앙값이다.

그러면 정렬된 순서는 x_4, x_2, x_1, x_3, x_5 또는 그 역순인 x_5, x_3, x_1, x_2, x_4임이 보장된다. 중앙값 정보만으로는 어떤 순서와 그 역순을 구분하는 것이 불가능하다는 점에 유의하라. 어떤 세 원소에 대해서도 중앙값 질의의 결과는 순서를 뒤집어도 동일하기 때문이다.

당신의 프로그램은 \mathbf{T}개의 리스트(각각 \mathbf{N}개 원소)를 정렬해야 하며, 전체를 통틀어 중앙값 질의를 최대 \mathbf{Q}번만 사용할 수 있다 (즉, 리스트 하나당 평균적으로 \mathbf{Q} / \mathbf{T}번 질의). 각 테스트 케이스에서 올바른 순서 또는 그 역순을 찾아내면 정답으로 인정된다. 각 케이스의 실제 순서는 가능한 모든 순서 중에서 균등 무작위로 생성되며, 다른 어떤 정보와도 독립적이다.