Informatica Online Judge

  재미있는 정렬 [2276 / 08E4]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 3   Total Tried : 7


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[USACO(2018OPEN)]

Background

젖소 베시는 정렬에 대해서 배웠다.

베시는 특히 "Bubble Sort"와 "Quick Sort"에 흥미를 느꼈다.

베시는 이 두 가지 정렬의 구현을 모두 활용하여 새로운 정렬을 구현했다.

이 정렬은 A[...i]의 최댓값이 A[i+1...]의 최솟값보다 크지 않으면 i, i+1을 분할할 수 있는 분할점(Partition Point)라고 부른다.

각 분할점을 찾고, 분할점을 기점으로 분할된 영역을 다시 재귀적으로 실행하여 정렬하도록 구현하고자 했다. 하지만 이 부분을 빠르게 구현하는 방법을 까먹어버렸다.

그 구현 코드는 다음과 같이 2가지 함수로 구현된다.

먼저 버블정렬의 아이디어를 활용한 함수

bubble_sort_pass (A) {
for i = 0 to length(A)-2
if A[i] > A[i+1], swap A[i] and A[i+1]
}


분할점을 찾고 재귀적으로 해결하는 함수

quickish_sort (A) {
if length(A) = 1, return
do { // Main loop
work_counter = work_counter + length(A)
bubble_sort_pass(A)
} while (no partition points exist in A)
divide A at all partition points; recursively quickish_sort each piece
}


베시는 이 알고리즘이 얼마나 빠르게 실행될지 궁금해서 메인루프에 work_counter이라는 전역변수를 두어 알고리즘의 수행빈도를 조사하려고 한다.

주어진 입력값에 대해서 work_counter을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 자료의 수를 나타내는 자연수 N이 입력된다.

그 다음 N줄에 걸쳐서 각 원소값이 한 줄에 하나씩 주어진다.

[입력값의 정의역]
1 <= N <= 100,000
0 <= 원소값 <= 10^9

Output

work_counter의 값을 출력한다.

IO Example

입력
7
20
2
3
4
9
8
7

출력
12

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]