結果

問題 No.2424 Josouzai
ユーザー osada-yumosada-yum
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

module merge_sort_m
use, intrinsic :: iso_fortran_env
implicit none
private
public :: merge_sort, merge_sort_descending
interface merge_sort
module procedure :: merge_sort_int32
module procedure :: merge_sort_with_key_int32
end interface merge_sort
interface merge_sort_descending
module procedure :: merge_sort_int32_descending
module procedure :: merge_sort_with_key_int32_descending
end interface merge_sort_descending
interface merge_sort
module procedure :: merge_sort_int64
module procedure :: merge_sort_with_key_int64
end interface merge_sort
interface merge_sort_descending
module procedure :: merge_sort_int64_descending
module procedure :: merge_sort_with_key_int64_descending
end interface merge_sort_descending
contains
!> 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, r
integer(int32) :: Left(1:q-p+1), Right(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = arr(p:q)
Right(1:r_max) = arr(q+1:r)
i = 1
j = 1
do k = p, r
if (Left(i) <= Right(j)) then
arr(k) = Left(i)
i = i + 1
if (i > l_max) then
arr(k+1:r) = Right(j:)
return
end if
else
arr(k) = Right(j)
j = j + 1
if (j > r_max) then
arr(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end 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, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call merge_sort_sub_int32(arr, p, q)
call merge_sort_sub_int32(arr, q+1, r)
call merge_int32(arr, p, q, r)
end if
end 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, r
integer(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_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(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 = 1
j = 1
do k = p, r
if (Left_key(i) <= Right_key(j)) then
key(k) = Left_key(i)
indices(k) = Left(i)
i = i + 1
if (i > l_max) then
key(k+1:r) = Right_key(j:)
indices(k+1:r) = Right(j:)
return
end if
else
key(k) = Right_key(j)
indices(k) = Right(j)
j = j + 1
if (j > r_max) then
key(k+1:r) = Left_key(i:)
indices(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end 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, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call 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 if
end 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, r
integer(int32) :: Left(1:q-p+1), Right(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = arr(p:q)
Right(1:r_max) = arr(q+1:r)
i = 1
j = 1
do k = p, r
if (Left(i) >= Right(j)) then
arr(k) = Left(i)
i = i + 1
if (i > l_max) then
arr(k+1:r) = Right(j:)
return
end if
else
arr(k) = Right(j)
j = j + 1
if (j > r_max) then
arr(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end 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, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call 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 if
end 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, r
integer(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_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(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 = 1
j = 1
do k = p, r
if (Left_key(i) >= Right_key(j)) then
key(k) = Left_key(i)
indices(k) = Left(i)
i = i + 1
if (i > l_max) then
key(k+1:r) = Right_key(j:)
indices(k+1:r) = Right(j:)
return
end if
else
key(k) = Right_key(j)
indices(k) = Right(j)
j = j + 1
if (j > r_max) then
key(k+1:r) = Left_key(i:)
indices(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end 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, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call 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 if
end 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, r
integer(int64) :: Left(1:q-p+1), Right(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = arr(p:q)
Right(1:r_max) = arr(q+1:r)
i = 1
j = 1
do k = p, r
if (Left(i) <= Right(j)) then
arr(k) = Left(i)
i = i + 1
if (i > l_max) then
arr(k+1:r) = Right(j:)
return
end if
else
arr(k) = Right(j)
j = j + 1
if (j > r_max) then
arr(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end 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, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call merge_sort_sub_int64(arr, p, q)
call merge_sort_sub_int64(arr, q+1, r)
call merge_int64(arr, p, q, r)
end if
end 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, r
integer(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_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(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 = 1
j = 1
do k = p, r
if (Left_key(i) <= Right_key(j)) then
key(k) = Left_key(i)
indices(k) = Left(i)
i = i + 1
if (i > l_max) then
key(k+1:r) = Right_key(j:)
indices(k+1:r) = Right(j:)
return
end if
else
key(k) = Right_key(j)
indices(k) = Right(j)
j = j + 1
if (j > r_max) then
key(k+1:r) = Left_key(i:)
indices(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end 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, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call 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 if
end 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, r
integer(int64) :: Left(1:q-p+1), Right(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = arr(p:q)
Right(1:r_max) = arr(q+1:r)
i = 1
j = 1
do k = p, r
if (Left(i) >= Right(j)) then
arr(k) = Left(i)
i = i + 1
if (i > l_max) then
arr(k+1:r) = Right(j:)
return
end if
else
arr(k) = Right(j)
j = j + 1
if (j > r_max) then
arr(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end 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, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call 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 if
end 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, r
integer(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_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(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 = 1
j = 1
do k = p, r
if (Left_key(i) >= Right_key(j)) then
key(k) = Left_key(i)
indices(k) = Left(i)
i = i + 1
if (i > l_max) then
key(k+1:r) = Right_key(j:)
indices(k+1:r) = Right(j:)
return
end if
else
key(k) = Right_key(j)
indices(k) = Right(j)
j = j + 1
if (j > r_max) then
key(k+1:r) = Left_key(i:)
indices(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end 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, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call 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 if
end subroutine merge_sort_sub_with_key_int64_descending
end module merge_sort_m
program yukicoder_2424
use, intrinsic :: iso_fortran_env
use merge_sort_m
implicit none
integer(int32) :: n, k, rest, cnts
integer(int32), allocatable :: arr(:)
integer(int32) :: i
read(input_unit, *) n, k
allocate(arr(n))
read(input_unit, *) arr(:)
call merge_sort(arr)
rest = k
cnts = 0_int32
do i = 1, n
if (rest < arr(i)) exit
rest = rest - arr(i)
cnts = cnts + 1
end do
write(output_unit, '(*(i0, 1x))') cnts, rest
end program yukicoder_2424
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0