이 문제에서는 서로 다른 정수 \mathbf{N} = 100개로 이루어진 리스트를 엄격히 증가하는 순서로 정렬해야 한다. 당신은 (서로 인접할 필요 없이) 임의의 두 위치에 있는 값을 서로 맞바꾸는 swap 연산으로 리스트를 재배열할 수 있다. 하지만 각 위치의 값을 직접 읽을 수는 없다. 대신, 연속한 구간에 대한 "최솟값 질의"를 통해 리스트에 대한 정보를 얻을 수 있다. 최솟값 질의는 연속 구간에서 최솟값을 가지는 원소의 위치를 반환한다. 예를 들어 리스트가 [51, 33, 100, 11]이라면, (1부터 세는) 2번부터 4번 위치까지의 최솟값은 4번 위치에 있고, 1번부터 3번 위치까지의 최솟값은 2번 위치에 있다.

구간의 최솟값을 묻는 질의는 테스트 케이스마다 주어지는 코인 예산에 의해 제한된다. 구간이 길수록 더 싸다. 즉, i \lt j일 때 i번부터 j번 위치까지(양 끝 포함) 최솟값의 위치를 묻는 데 드는 비용은 \lceil 10^8 / (j - i + 1) \rceil 코인이다. 여기서 \lceil x \rceil는 x 이상인 최소의 정수(즉 올림)이다. 반면 swap 연산은 코인을 전혀 소모하지 않는다.

각 테스트 케이스마다, 임의의 횟수의 swap과 최댓값이 6 \times 10^8 코인인 예산 안에서(임의의 횟수의) 최솟값 질의를 사용하여 리스트를 정렬하는 프로그램을 작성하라.

#10404 upload - done - how_to_reg - component_exchange Interactive stop_circle Grading on hold

Minimum Sort timer 60s memory 1024MB

#10404
Interactive

Grading on hold

Minimum Sort 60s 1024MB