Submission #7530291


Source Code Expand

Copy
module mod_priority_queue
  implicit none
  type t_priority_queue
    private
    integer :: num = 0 !中に入ってる物の数
    integer, pointer :: heap(:) => null()!pqの容量
  contains
    procedure :: offer => offer
    procedure :: clear => clear
    procedure :: poll => poll
    procedure :: peek => peek
    procedure :: size => size_of
  end type t_priority_queue
  
contains
 
  subroutine offer(pq,item)
    class(t_priority_queue), intent(inout) :: pq
    integer, intent(in) :: item
    integer :: n, i, t
    integer, allocatable :: tmp(:)
    if (.not.associated(pq%heap)) allocate(pq%heap(1))
    
    !いっぱいいっぱいのときには拡張している
    if (pq%num == size(pq%heap)) then
      allocate(tmp(pq%num))
      tmp = pq%heap
      deallocate(pq%heap)
      allocate(pq%heap(2*pq%num))
      pq%heap(1:pq%num) = tmp
      deallocate(tmp)
    end if
    
    pq%num = pq%num+1
    pq%heap(pq%num) = item
    n = pq%num
    do while (n > 1)
      i = n/2
      if (pq%heap(n) > pq%heap(i)) then
        t = pq%heap(n)
        pq%heap(n) = pq%heap(i)
        pq%heap(i) = t
      end if
      n = i
    end do
    return
  end subroutine offer
  
  subroutine clear(pq)
    class(t_priority_queue), intent(inout) :: pq
    if (associated(pq%heap)) deallocate(pq%heap)
    pq%num = 0
    return
  end subroutine clear
 
  function poll(pq) result(item)
    class(t_priority_queue), intent(inout) :: pq
    integer :: item, n, i, j, tmp
    n = pq%num
    item = pq%heap(1)
    pq%heap(1) = pq%heap(n)
    pq%num = pq%num-1
    i = 1
    do while (2*i < n)
      j = 2*i
      if (j+1 < n .and. pq%heap(j+1) > pq%heap(j)) j = j+1
      if (pq%heap(j) > pq%heap(i)) then
        tmp = pq%heap(j)
        pq%heap(j) = pq%heap(i)
        pq%heap(i) = tmp
      end if
      i = j
    end do
  end function poll
  
  function peek(pq) result(item)
    class(t_priority_queue), intent(inout) :: pq
    integer :: item
    item = pq%heap(1)
  end function peek
  
  integer function size_of(pq)
    class(t_priority_queue), intent(in) :: pq
    size_of = pq%num
  end function size_of
end module mod_priority_queue
 
use mod_priority_queue
integer N,M
integer,allocatable,dimension(:)::A
type(t_priority_queue) :: pq
integer(16) ans
integer tmp

read*,N,M
allocate(A(N))
read*,A
do i=1,N
  call offer(pq,A(i))
end do
do i=1,M
  tmp=poll(pq)
  tmp=tmp/2
  call offer(pq,tmp)
end do

ans=0
do i=1,N
  ans=ans+poll(pq)
end do
print"(i0)",ans
end

Submission Info

Submission Time
Task D - Powerful Discount Tickets
User Shizuku
Language Fortran (gfortran v4.8.4)
Score 400
Code Size 2586 Byte
Status AC
Exec Time 64 ms
Memory 1760 KB

Judge Result

Set Name All Sample
Score / Max Score 400 / 400 0 / 0
Status
AC × 23
AC × 4
Set Name Test Cases
All sample_01, sample_02, sample_03, sample_04, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18, testcase_19
Sample sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sample_03 AC 2 ms 256 KB
sample_04 AC 1 ms 256 KB
testcase_01 AC 32 ms 1376 KB
testcase_02 AC 17 ms 384 KB
testcase_03 AC 50 ms 1760 KB
testcase_04 AC 64 ms 1760 KB
testcase_05 AC 21 ms 1248 KB
testcase_06 AC 50 ms 1760 KB
testcase_07 AC 10 ms 768 KB
testcase_08 AC 49 ms 1760 KB
testcase_09 AC 39 ms 1248 KB
testcase_10 AC 15 ms 640 KB
testcase_11 AC 38 ms 1504 KB
testcase_12 AC 58 ms 1760 KB
testcase_13 AC 13 ms 256 KB
testcase_14 AC 53 ms 1760 KB
testcase_15 AC 64 ms 1760 KB
testcase_16 AC 19 ms 512 KB
testcase_17 AC 1 ms 256 KB
testcase_18 AC 1 ms 256 KB
testcase_19 AC 42 ms 1760 KB