結果
問題 | No.2424 Josouzai |
ユーザー |
|
提出日時 | 2023-08-18 21:31:18 |
言語 | Fortran (gFortran 14.2.0) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 21,931 bytes |
コンパイル時間 | 1,666 ms |
コンパイル使用メモリ | 44,016 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-28 05:48:06 |
合計ジャッジ時間 | 3,472 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
module merge_sort_muse, intrinsic :: iso_fortran_envimplicit noneprivatepublic :: merge_sort, merge_sort_descendinginterface merge_sortmodule procedure :: merge_sort_int32module procedure :: merge_sort_with_key_int32end interface merge_sortinterface merge_sort_descendingmodule procedure :: merge_sort_int32_descendingmodule procedure :: merge_sort_with_key_int32_descendingend interface merge_sort_descendinginterface merge_sortmodule procedure :: merge_sort_int64module procedure :: merge_sort_with_key_int64end interface merge_sortinterface merge_sort_descendingmodule procedure :: merge_sort_int64_descendingmodule procedure :: merge_sort_with_key_int64_descendingend interface merge_sort_descendingcontains!> merge_sort_int32: Sort arr(:) by sub function merge_sort_sub_int32.!> arguments:!> arr: array of some type.subroutine merge_sort_int32(arr)integer(int32), intent(inout) :: arr(:)call merge_sort_sub_int32(arr, 1, size(arr))end subroutine merge_sort_int32!> merge: Algorithm for merge_sort, check if Left or Right is end in each loop.!> arguments:!> arr: array of some type, (out) arr(p:r) is sorted.!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).!> variables:!> Left, Right: array of typeof(arr), sorted!> l_max, r_max: integer, max index of Left or Right.subroutine merge_int32(arr, p, q, r)integer(int32), intent(inout) :: arr(:)integer(int32), intent(in) :: p, q, rinteger(int32) :: Left(1:q-p+1), Right(1:r-q)integer(int32) :: l_max, r_maxl_max = q-p+1r_max = r-qblock!> i, j, k: integer, loop counters.integer(int32) :: i, j, kLeft(1:l_max) = arr(p:q)Right(1:r_max) = arr(q+1:r)i = 1j = 1do k = p, rif (Left(i) <= Right(j)) thenarr(k) = Left(i)i = i + 1if (i > l_max) thenarr(k+1:r) = Right(j:)returnend ifelsearr(k) = Right(j)j = j + 1if (j > r_max) thenarr(k+1:r) = Left(i:)returnend ifend ifend doend blockend subroutine merge_int32!> merge_sort_sub: Recursive function used by merge_sort.!> arguments:!> arr: array of some type.!> p, r: integer, p is start of arr, r is end of arr.!> variables:!> q: integer, q = floor( (p+q)/2 )recursive subroutine merge_sort_sub_int32(arr, p, r)integer(int32), intent(inout) :: arr(:)integer(int32), intent(in) :: p, rinteger(int32) :: qif (p < r) thenq = (p+r)/2call merge_sort_sub_int32(arr, p, q)call merge_sort_sub_int32(arr, q+1, r)call merge_int32(arr, p, q, r)end ifend subroutine merge_sort_sub_int32!> merge_sort_with_key_int32: Sort key(:) sub function merge_sort_sub_with_key_int32.!> arguments:!> key: array of some type.!> indices: array of some type.subroutine merge_sort_with_key_int32(key, indices)integer(int32), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)call merge_sort_sub_with_key_int32(key, indices, 1, size(key))end subroutine merge_sort_with_key_int32!> merge_with_key: Algorithm for merge_sort, check if Left or Right is end in each loop.!> arguments:!> indices: array of indices.!> key: array of some type, (out) key(p:r) is sorted.!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).!> variables:!> Left, Right: array of typeof(indices), sorted!> l_max, r_max: integer, max index of Left or Right.subroutine merge_with_key_int32(key, indices, p, q, r)integer(int32), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)integer(int32), intent(in) :: p, q, rinteger(int32) :: Left(1:q-p+1), Right(1:r-q)integer(int32) :: Left_key(1:q-p+1), Right_key(1:r-q)integer(int32) :: l_max, r_maxl_max = q-p+1r_max = r-qblock!> i, j, k: integer, loop counters.integer(int32) :: i, j, kLeft(1:l_max) = indices(p:q)Right(1:r_max) = indices(q+1:r)Left_key(1:l_max) = key(p:q)Right_key(1:r_max) = key(q+1:r)i = 1j = 1do k = p, rif (Left_key(i) <= Right_key(j)) thenkey(k) = Left_key(i)indices(k) = Left(i)i = i + 1if (i > l_max) thenkey(k+1:r) = Right_key(j:)indices(k+1:r) = Right(j:)returnend ifelsekey(k) = Right_key(j)indices(k) = Right(j)j = j + 1if (j > r_max) thenkey(k+1:r) = Left_key(i:)indices(k+1:r) = Left(i:)returnend ifend ifend doend blockend subroutine merge_with_key_int32!> merge_sort_sub_with_key: Recursive function used by merge_sort_with_key.!> arguments:!> indices: array of indices.!> key: array of some type.!> p, r: integer, p is start of arr, r is end of arr.!> variables:!> q: integer, q = floor( (p+q)/2 )recursive subroutine merge_sort_sub_with_key_int32(key, indices, p, r)integer(int32), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)integer(int32), intent(in) :: p, rinteger(int32) :: qif (p < r) thenq = (p+r)/2call merge_sort_sub_with_key_int32(key, indices, p, q)call merge_sort_sub_with_key_int32(key, indices, q+1, r)call merge_with_key_int32(key, indices, p, q, r)end ifend subroutine merge_sort_sub_with_key_int32!> merge_sort_int32_descending: Sort arr(:) by sub function merge_sort_sub_int32_descending.!> arguments:!> arr: array of some type.subroutine merge_sort_int32_descending(arr)integer(int32), intent(inout) :: arr(:)call merge_sort_sub_int32_descending(arr, 1, size(arr))end subroutine merge_sort_int32_descending!> merge: Algorithm for merge_sort, check if Left or Right is end in each loop.!> arguments:!> arr: array of some type, (out) arr(p:r) is sorted.!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).!> variables:!> Left, Right: array of typeof(arr), sorted!> l_max, r_max: integer, max index of Left or Right.subroutine merge_int32_descending(arr, p, q, r)integer(int32), intent(inout) :: arr(:)integer(int32), intent(in) :: p, q, rinteger(int32) :: Left(1:q-p+1), Right(1:r-q)integer(int32) :: l_max, r_maxl_max = q-p+1r_max = r-qblock!> i, j, k: integer, loop counters.integer(int32) :: i, j, kLeft(1:l_max) = arr(p:q)Right(1:r_max) = arr(q+1:r)i = 1j = 1do k = p, rif (Left(i) >= Right(j)) thenarr(k) = Left(i)i = i + 1if (i > l_max) thenarr(k+1:r) = Right(j:)returnend ifelsearr(k) = Right(j)j = j + 1if (j > r_max) thenarr(k+1:r) = Left(i:)returnend ifend ifend doend blockend subroutine merge_int32_descending!> merge_sort_sub: Recursive function used by merge_sort.!> arguments:!> arr: array of some type.!> p, r: integer, p is start of arr, r is end of arr.!> variables:!> q: integer, q = floor( (p+q)/2 )recursive subroutine merge_sort_sub_int32_descending(arr, p, r)integer(int32), intent(inout) :: arr(:)integer(int32), intent(in) :: p, rinteger(int32) :: qif (p < r) thenq = (p+r)/2call merge_sort_sub_int32_descending(arr, p, q)call merge_sort_sub_int32_descending(arr, q+1, r)call merge_int32_descending(arr, p, q, r)end ifend subroutine merge_sort_sub_int32_descending!> merge_sort_with_key_int32_descending: Sort key(:) sub function merge_sort_sub_with_key_int32_descending.!> arguments:!> key: array of some type.!> indices: array of some type.subroutine merge_sort_with_key_int32_descending(key, indices)integer(int32), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)call merge_sort_sub_with_key_int32_descending(key, indices, 1, size(key))end subroutine merge_sort_with_key_int32_descending!> merge_with_key: Algorithm for merge_sort, check if Left or Right is end in each loop.!> arguments:!> indices: array of indices.!> key: array of some type, (out) key(p:r) is sorted.!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).!> variables:!> Left, Right: array of typeof(indices), sorted!> l_max, r_max: integer, max index of Left or Right.subroutine merge_with_key_int32_descending(key, indices, p, q, r)integer(int32), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)integer(int32), intent(in) :: p, q, rinteger(int32) :: Left(1:q-p+1), Right(1:r-q)integer(int32) :: Left_key(1:q-p+1), Right_key(1:r-q)integer(int32) :: l_max, r_maxl_max = q-p+1r_max = r-qblock!> i, j, k: integer, loop counters.integer(int32) :: i, j, kLeft(1:l_max) = indices(p:q)Right(1:r_max) = indices(q+1:r)Left_key(1:l_max) = key(p:q)Right_key(1:r_max) = key(q+1:r)i = 1j = 1do k = p, rif (Left_key(i) >= Right_key(j)) thenkey(k) = Left_key(i)indices(k) = Left(i)i = i + 1if (i > l_max) thenkey(k+1:r) = Right_key(j:)indices(k+1:r) = Right(j:)returnend ifelsekey(k) = Right_key(j)indices(k) = Right(j)j = j + 1if (j > r_max) thenkey(k+1:r) = Left_key(i:)indices(k+1:r) = Left(i:)returnend ifend ifend doend blockend subroutine merge_with_key_int32_descending!> merge_sort_sub_with_key: Recursive function used by merge_sort_with_key.!> arguments:!> indices: array of indices.!> key: array of some type.!> p, r: integer, p is start of arr, r is end of arr.!> variables:!> q: integer, q = floor( (p+q)/2 )recursive subroutine merge_sort_sub_with_key_int32_descending(key, indices, p, r)integer(int32), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)integer(int32), intent(in) :: p, rinteger(int32) :: qif (p < r) thenq = (p+r)/2call merge_sort_sub_with_key_int32_descending(key, indices, p, q)call merge_sort_sub_with_key_int32_descending(key, indices, q+1, r)call merge_with_key_int32_descending(key, indices, p, q, r)end ifend subroutine merge_sort_sub_with_key_int32_descending!> merge_sort_int64: Sort arr(:) by sub function merge_sort_sub_int64.!> arguments:!> arr: array of some type.subroutine merge_sort_int64(arr)integer(int64), intent(inout) :: arr(:)call merge_sort_sub_int64(arr, 1, size(arr))end subroutine merge_sort_int64!> merge: Algorithm for merge_sort, check if Left or Right is end in each loop.!> arguments:!> arr: array of some type, (out) arr(p:r) is sorted.!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).!> variables:!> Left, Right: array of typeof(arr), sorted!> l_max, r_max: integer, max index of Left or Right.subroutine merge_int64(arr, p, q, r)integer(int64), intent(inout) :: arr(:)integer(int32), intent(in) :: p, q, rinteger(int64) :: Left(1:q-p+1), Right(1:r-q)integer(int32) :: l_max, r_maxl_max = q-p+1r_max = r-qblock!> i, j, k: integer, loop counters.integer(int32) :: i, j, kLeft(1:l_max) = arr(p:q)Right(1:r_max) = arr(q+1:r)i = 1j = 1do k = p, rif (Left(i) <= Right(j)) thenarr(k) = Left(i)i = i + 1if (i > l_max) thenarr(k+1:r) = Right(j:)returnend ifelsearr(k) = Right(j)j = j + 1if (j > r_max) thenarr(k+1:r) = Left(i:)returnend ifend ifend doend blockend subroutine merge_int64!> merge_sort_sub: Recursive function used by merge_sort.!> arguments:!> arr: array of some type.!> p, r: integer, p is start of arr, r is end of arr.!> variables:!> q: integer, q = floor( (p+q)/2 )recursive subroutine merge_sort_sub_int64(arr, p, r)integer(int64), intent(inout) :: arr(:)integer(int32), intent(in) :: p, rinteger(int32) :: qif (p < r) thenq = (p+r)/2call merge_sort_sub_int64(arr, p, q)call merge_sort_sub_int64(arr, q+1, r)call merge_int64(arr, p, q, r)end ifend subroutine merge_sort_sub_int64!> merge_sort_with_key_int64: Sort key(:) sub function merge_sort_sub_with_key_int64.!> arguments:!> key: array of some type.!> indices: array of some type.subroutine merge_sort_with_key_int64(key, indices)integer(int64), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)call merge_sort_sub_with_key_int64(key, indices, 1, size(key))end subroutine merge_sort_with_key_int64!> merge_with_key: Algorithm for merge_sort, check if Left or Right is end in each loop.!> arguments:!> indices: array of indices.!> key: array of some type, (out) key(p:r) is sorted.!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).!> variables:!> Left, Right: array of typeof(indices), sorted!> l_max, r_max: integer, max index of Left or Right.subroutine merge_with_key_int64(key, indices, p, q, r)integer(int64), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)integer(int32), intent(in) :: p, q, rinteger(int32) :: Left(1:q-p+1), Right(1:r-q)integer(int64) :: Left_key(1:q-p+1), Right_key(1:r-q)integer(int32) :: l_max, r_maxl_max = q-p+1r_max = r-qblock!> i, j, k: integer, loop counters.integer(int32) :: i, j, kLeft(1:l_max) = indices(p:q)Right(1:r_max) = indices(q+1:r)Left_key(1:l_max) = key(p:q)Right_key(1:r_max) = key(q+1:r)i = 1j = 1do k = p, rif (Left_key(i) <= Right_key(j)) thenkey(k) = Left_key(i)indices(k) = Left(i)i = i + 1if (i > l_max) thenkey(k+1:r) = Right_key(j:)indices(k+1:r) = Right(j:)returnend ifelsekey(k) = Right_key(j)indices(k) = Right(j)j = j + 1if (j > r_max) thenkey(k+1:r) = Left_key(i:)indices(k+1:r) = Left(i:)returnend ifend ifend doend blockend subroutine merge_with_key_int64!> merge_sort_sub_with_key: Recursive function used by merge_sort_with_key.!> arguments:!> indices: array of indices.!> key: array of some type.!> p, r: integer, p is start of arr, r is end of arr.!> variables:!> q: integer, q = floor( (p+q)/2 )recursive subroutine merge_sort_sub_with_key_int64(key, indices, p, r)integer(int64), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)integer(int32), intent(in) :: p, rinteger(int32) :: qif (p < r) thenq = (p+r)/2call merge_sort_sub_with_key_int64(key, indices, p, q)call merge_sort_sub_with_key_int64(key, indices, q+1, r)call merge_with_key_int64(key, indices, p, q, r)end ifend subroutine merge_sort_sub_with_key_int64!> merge_sort_int64_descending: Sort arr(:) by sub function merge_sort_sub_int64_descending.!> arguments:!> arr: array of some type.subroutine merge_sort_int64_descending(arr)integer(int64), intent(inout) :: arr(:)call merge_sort_sub_int64_descending(arr, 1, size(arr))end subroutine merge_sort_int64_descending!> merge: Algorithm for merge_sort, check if Left or Right is end in each loop.!> arguments:!> arr: array of some type, (out) arr(p:r) is sorted.!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).!> variables:!> Left, Right: array of typeof(arr), sorted!> l_max, r_max: integer, max index of Left or Right.subroutine merge_int64_descending(arr, p, q, r)integer(int64), intent(inout) :: arr(:)integer(int32), intent(in) :: p, q, rinteger(int64) :: Left(1:q-p+1), Right(1:r-q)integer(int32) :: l_max, r_maxl_max = q-p+1r_max = r-qblock!> i, j, k: integer, loop counters.integer(int32) :: i, j, kLeft(1:l_max) = arr(p:q)Right(1:r_max) = arr(q+1:r)i = 1j = 1do k = p, rif (Left(i) >= Right(j)) thenarr(k) = Left(i)i = i + 1if (i > l_max) thenarr(k+1:r) = Right(j:)returnend ifelsearr(k) = Right(j)j = j + 1if (j > r_max) thenarr(k+1:r) = Left(i:)returnend ifend ifend doend blockend subroutine merge_int64_descending!> merge_sort_sub: Recursive function used by merge_sort.!> arguments:!> arr: array of some type.!> p, r: integer, p is start of arr, r is end of arr.!> variables:!> q: integer, q = floor( (p+q)/2 )recursive subroutine merge_sort_sub_int64_descending(arr, p, r)integer(int64), intent(inout) :: arr(:)integer(int32), intent(in) :: p, rinteger(int32) :: qif (p < r) thenq = (p+r)/2call merge_sort_sub_int64_descending(arr, p, q)call merge_sort_sub_int64_descending(arr, q+1, r)call merge_int64_descending(arr, p, q, r)end ifend subroutine merge_sort_sub_int64_descending!> merge_sort_with_key_int64_descending: Sort key(:) sub function merge_sort_sub_with_key_int64_descending.!> arguments:!> key: array of some type.!> indices: array of some type.subroutine merge_sort_with_key_int64_descending(key, indices)integer(int64), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)call merge_sort_sub_with_key_int64_descending(key, indices, 1, size(key))end subroutine merge_sort_with_key_int64_descending!> merge_with_key: Algorithm for merge_sort, check if Left or Right is end in each loop.!> arguments:!> indices: array of indices.!> key: array of some type, (out) key(p:r) is sorted.!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).!> variables:!> Left, Right: array of typeof(indices), sorted!> l_max, r_max: integer, max index of Left or Right.subroutine merge_with_key_int64_descending(key, indices, p, q, r)integer(int64), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)integer(int32), intent(in) :: p, q, rinteger(int32) :: Left(1:q-p+1), Right(1:r-q)integer(int64) :: Left_key(1:q-p+1), Right_key(1:r-q)integer(int32) :: l_max, r_maxl_max = q-p+1r_max = r-qblock!> i, j, k: integer, loop counters.integer(int32) :: i, j, kLeft(1:l_max) = indices(p:q)Right(1:r_max) = indices(q+1:r)Left_key(1:l_max) = key(p:q)Right_key(1:r_max) = key(q+1:r)i = 1j = 1do k = p, rif (Left_key(i) >= Right_key(j)) thenkey(k) = Left_key(i)indices(k) = Left(i)i = i + 1if (i > l_max) thenkey(k+1:r) = Right_key(j:)indices(k+1:r) = Right(j:)returnend ifelsekey(k) = Right_key(j)indices(k) = Right(j)j = j + 1if (j > r_max) thenkey(k+1:r) = Left_key(i:)indices(k+1:r) = Left(i:)returnend ifend ifend doend blockend subroutine merge_with_key_int64_descending!> merge_sort_sub_with_key: Recursive function used by merge_sort_with_key.!> arguments:!> indices: array of indices.!> key: array of some type.!> p, r: integer, p is start of arr, r is end of arr.!> variables:!> q: integer, q = floor( (p+q)/2 )recursive subroutine merge_sort_sub_with_key_int64_descending(key, indices, p, r)integer(int64), intent(inout) :: key(:)integer(int32), intent(inout) :: indices(:)integer(int32), intent(in) :: p, rinteger(int32) :: qif (p < r) thenq = (p+r)/2call merge_sort_sub_with_key_int64_descending(key, indices, p, q)call merge_sort_sub_with_key_int64_descending(key, indices, q+1, r)call merge_with_key_int64_descending(key, indices, p, q, r)end ifend subroutine merge_sort_sub_with_key_int64_descendingend module merge_sort_mprogram yukicoder_2424use, intrinsic :: iso_fortran_envuse merge_sort_mimplicit noneinteger(int32) :: n, k, rest, cntsinteger(int32), allocatable :: arr(:)integer(int32) :: iread(input_unit, *) n, kallocate(arr(n))read(input_unit, *) arr(:)call merge_sort(arr)rest = kcnts = 0_int32do i = 1, nif (rest < arr(i)) exitrest = rest - arr(i)cnts = cnts + 1end dowrite(output_unit, '(*(i0, 1x))') cnts, restend program yukicoder_2424