結果

問題 No.2835 Take and Flip
コンテスト
ユーザー osada-yum
提出日時 2024-10-31 02:02:19
言語 Fortran
(gFortran 14.2.0)
結果
AC  
実行時間 116 ms / 2,000 ms
コード長 4,740 bytes
コンパイル時間 2,222 ms
コンパイル使用メモリ 39,680 KB
実行使用メモリ 8,760 KB
最終ジャッジ日時 2024-10-31 02:02:25
合計ジャッジ時間 5,206 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

!> This file was processed by `fypp`.
!> Today's fortune: "Bad WA", really OK?
!> ランダムウォーク猿「'BFS' で はっぴー.」
!> ギャンブラー猿「AtCoder は運だ.」

module merge_sort_m
  use, intrinsic :: iso_fortran_env
  !> maybe use module.
  implicit none
  private
  public :: merge_sort
  interface merge_sort
     module procedure :: merge_sort_int64
  end interface merge_sort
contains
  pure subroutine merge_sort_int64(arr, indices, reverse)
    integer(int64), intent(inout) :: arr(:)
    integer(int32), intent(inout), optional :: indices(:)
    logical, intent(in), optional :: reverse
    integer(int32), allocatable :: idx(:)
    integer(int32) :: n
    integer(int32) :: i
    n = size(arr)
    allocate(idx, source = [(i, i = 1, n)])
    if (present(reverse)) then
       if (reverse) then
          call merge_sort_sub_descending(n, arr, idx)
          if (present(indices)) &
               indices(:) = idx(:)
          return
       end if
    end if
    call merge_sort_sub_ascending(n, arr, idx)
    if (present(indices)) &
         indices(:) = idx(:)
    return
  contains
    pure subroutine merge_sort_sub_ascending(n, arr, idx)
      integer(int32), intent(in) :: n
      integer(int64), intent(inout) :: arr(n)
      integer(int32), intent(inout) :: idx(n)
      integer(int32) :: width
      integer(int32) :: i, l, r
      width = 2
      do while (width <= 2 * n)
         do i = 1, n, width
            if (i + width / 2 > n) exit
            l = i
            r = min(n, i + width - 1)
            call merge_sort_int64_merge_with_key_ascending(r - l + 1, width/2, arr(l:r), idx(l:r))
         end do
         width = width * 2
      end do
    end subroutine merge_sort_sub_ascending
    pure subroutine merge_sort_sub_descending(n, arr, idx)
      integer(int32), intent(in) :: n
      integer(int64), intent(inout) :: arr(n)
      integer(int32), intent(inout) :: idx(n)
      integer(int32) :: width
      integer(int32) :: i, l, r
      width = 2
      do while (width <= 2 * n)
         do i = 1, n, width
            if (i + width / 2 > n) exit
            l = i
            r = min(n, i + width - 1)
            call merge_sort_int64_merge_with_key_descending(r - l + 1, width/2, arr(l:r), idx(l:r))
         end do
         width = width * 2
      end do
    end subroutine merge_sort_sub_descending
  end subroutine merge_sort_int64
  pure subroutine merge_sort_int64_merge_with_key_ascending(n, nl, arr, indices)
    integer(int32), intent(in) :: n, nl
    integer(int64), intent(inout) :: arr(n)
    integer(int32), intent(inout) :: indices(n)
    integer(int32) :: idx_left(1:nl), idx_right(nl + 1:n)
    integer(int32) :: idx(n)
    integer(int32) :: i, j, k
    if (n == 1) return
    idx_left(1:nl) = [(i, i = 1, nl)]
    idx_right(nl + 1:n) = [(i, i = nl + 1, n)]
    i = 1
    j = nl + 1
    do k = 1, n
       if (arr(i) <= arr(j)) then
          idx(k) = idx_left(i)
          i = i + 1
       else
          idx(k) = idx_right(j)
          j = j + 1
       end if
       if (i > nl) then
          idx(k + 1:n) = idx_right(j:n)
          exit
       else if (j > n) then
          idx(k + 1:n) = idx_left(i:nl)
          exit
       end if
    end do
    arr(:) = arr(idx)
    indices(:) = indices(idx)
  end subroutine merge_sort_int64_merge_with_key_ascending
  pure subroutine merge_sort_int64_merge_with_key_descending(n, nl, arr, indices)
    integer(int32), intent(in) :: n, nl
    integer(int64), intent(inout) :: arr(n)
    integer(int32), intent(inout) :: indices(n)
    integer(int32) :: idx_left(1:nl), idx_right(nl + 1:n)
    integer(int32) :: idx(n)
    integer(int32) :: i, j, k
    if (n == 1) return
    idx_left(1:nl) = [(i, i = 1, nl)]
    idx_right(nl + 1:n) = [(i, i = nl + 1, n)]
    i = 1
    j = nl + 1
    do k = 1, n
       if (arr(i) >= arr(j)) then
          idx(k) = idx_left(i)
          i = i + 1
       else
          idx(k) = idx_right(j)
          j = j + 1
       end if
       if (i > nl) then
          idx(k + 1:n) = idx_right(j:n)
          exit
       else if (j > n) then
          idx(k + 1:n) = idx_left(i:nl)
          exit
       end if
    end do
    arr(:) = arr(idx)
    indices(:) = indices(idx)
  end subroutine merge_sort_int64_merge_with_key_descending
end module merge_sort_m
program yukicoder2835
  use, intrinsic :: iso_fortran_env
  !> auto use module
  use merge_sort_m
  use merge_sort_m
  implicit none
  integer(int32) :: n
  integer(int64), allocatable :: arr(:)
  read(input_unit, *) n
  allocate(arr(n))
  read(input_unit, *) arr(:)
  call merge_sort(arr)
  ! write(error_unit, '(*(g0, 1x))') arr(:)
  write(output_unit, '(i0)') sum(arr(n / 2 + 1 : n)) + sum(arr(1:n / 2))
end program yukicoder2835
0