結果
| 問題 | No.2424 Josouzai |
| ユーザー |
 osada-yum
|
| 提出日時 | 2023-08-18 21:31:18 |
| 言語 | Fortran (gFortran 13.2.0) |
| 結果 |
AC
|
| 実行時間 | 71 ms / 2,000 ms |
| コード長 | 21,931 bytes |
| コンパイル時間 | 1,719 ms |
| コンパイル使用メモリ | 43,904 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-05-06 03:23:44 |
| 合計ジャッジ時間 | 4,165 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,248 KB |
| testcase_02 | AC | 1 ms
5,248 KB |
| testcase_03 | AC | 1 ms
5,376 KB |
| testcase_04 | AC | 21 ms
5,376 KB |
| testcase_05 | AC | 71 ms
5,376 KB |
| testcase_06 | AC | 69 ms
5,376 KB |
| testcase_07 | AC | 66 ms
5,376 KB |
| testcase_08 | AC | 70 ms
5,376 KB |
| testcase_09 | AC | 1 ms
5,376 KB |
| testcase_10 | AC | 16 ms
5,376 KB |
| testcase_11 | AC | 43 ms
5,376 KB |
| testcase_12 | AC | 33 ms
5,376 KB |
| testcase_13 | AC | 21 ms
5,376 KB |
| testcase_14 | AC | 38 ms
5,376 KB |
| testcase_15 | AC | 6 ms
5,376 KB |
| testcase_16 | AC | 59 ms
5,376 KB |
| testcase_17 | AC | 16 ms
5,376 KB |
| testcase_18 | AC | 19 ms
5,376 KB |
| testcase_19 | AC | 32 ms
5,376 KB |
| testcase_20 | AC | 63 ms
5,376 KB |
| testcase_21 | AC | 48 ms
5,376 KB |
| testcase_22 | AC | 22 ms
5,376 KB |
| testcase_23 | AC | 28 ms
5,376 KB |
| testcase_24 | AC | 12 ms
5,376 KB |
| testcase_25 | AC | 64 ms
5,376 KB |
| testcase_26 | AC | 47 ms
5,376 KB |
| testcase_27 | AC | 67 ms
5,376 KB |
| testcase_28 | AC | 56 ms
5,376 KB |
| testcase_29 | AC | 50 ms
5,376 KB |
| testcase_30 | AC | 13 ms
5,376 KB |
| testcase_31 | AC | 29 ms
5,376 KB |
| testcase_32 | AC | 64 ms
5,376 KB |
ソースコード
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