이 문제에서는 서로 다른 정수 \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 코인인 예산 안에서(임의의 횟수의) 최솟값 질의를 사용하여
리스트를 정렬하는 프로그램을 작성하라.
ログインしないとコードを書けません。