All submissions for this problem are available.
Alice uses the following pseudocode when she needs to sort a permutation of N positive integers:
procedure Sort(list A) defined as:
list less, greater
if length(A) <= 1 then return A
pivot := A(length(A)+1) / 2
for i := 1 to length(A) do:
if Ai < pivot then append Ai to less else if Ai > pivot append Ai to greater
return concatenate(Sort(less), pivot, Sort(greater) )
And now we are interested in the number of comparisons that will be made during the sorting of the given permutation of integers A with the provided code. So, we ask you to find the value of the variable comparison_count after such a sorting.
The first line of input consists of a single integer N. The second line of input contains a permutation of N numbers.
Output the number of comparisons on the first and only line of the output.
Input: 5 4 3 5 1 2 Output: 11
ScoringSubtask 1 (32 points): 1 <= N <= 2000.
Subtask 2 (9 points): 1 <= N <= 105, the permutation is generated randomly.
Subtask 3 (45 points): 1 <= N <= 65536.
Subtask 4 (14 points): 1 <= N <= 5*105.
|Tags||easy-medium, ltime03, persistence, segment-tree, xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.