提出 #49183034

ソースコード 拡げる

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
program main
    implicit none
    integer(8) N, K, ok, ng, ref, cnt, ok_cnt, ng_cnt, ref_cnt, i
    integer(8), allocatable:: A(:), B(:)
    read*, N, K
    allocate(A(N))
    allocate(B(N))
    read*, A, B
    call heapsort(N, A)
    call heapsort(N, B)
    ng = 0
    ok = maxval(A) * maxval(B) + 1
    do while (abs(ng - ok) > 1)
        ref = (ng + ok) / 2
        !積がref以下になるものが何個あるか数える
        cnt = 0
        do i = 1, N
            ok_cnt = 0
            ng_cnt = N + 1
            do while (ng_cnt - ok_cnt > 1)
                ref_cnt = (ok_cnt + ng_cnt) / 2
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

program main
    implicit none
    integer(8) N, K, ok, ng, ref, cnt, ok_cnt, ng_cnt, ref_cnt, i
    integer(8), allocatable:: A(:), B(:)
    read*, N, K
    allocate(A(N))
    allocate(B(N))
    read*, A, B
    call heapsort(N, A)
    call heapsort(N, B)
    ng = 0
    ok = maxval(A) * maxval(B) + 1
    do while (abs(ng - ok) > 1)
        ref = (ng + ok) / 2
        !積がref以下になるものが何個あるか数える
        cnt = 0
        do i = 1, N
            ok_cnt = 0
            ng_cnt = N + 1
            do while (ng_cnt - ok_cnt > 1)
                ref_cnt = (ok_cnt + ng_cnt) / 2
                if (A(i) * B(ref_cnt) <= ref) then
                    ok_cnt = ref_cnt
                else
                    ng_cnt = ref_cnt
                end if
            end do
            cnt = cnt + ok_cnt
        end do

        if (cnt >= K) then
            ok = ref
        else
            ng = ref
        end if
    end do
    print'(i0)', ok
end program main

subroutine heapsort(n,array)
    implicit none
    integer(8),intent(in) :: n
    integer(8),intent(inout) :: array(1:n)

    integer(8) ::i,k,j,l
    integer(8) :: t

    if(n.eq.1)return

    l=n/2+1
    k=n
    do while(k.ne.1)
       if(l.gt.1)then
          l=l-1
          t=array(L)
       else
          t=array(k)
          array(k)=array(1)
          k=k-1
          if(k.eq.1) then
             array(1)=t
             exit
          endif
       endif
       i=l
       j=l+l
       do while(j.le.k)
          if(j.lt.k)then
             if(array(j).lt.array(j+1))j=j+1
          endif
          if (t.lt.array(j))then
             array(i)=array(j)
             i=j
             j=j+j
          else
             j=k+1
          endif
       enddo
       array(i)=t
    enddo

    return
end subroutine heapsort

提出情報

ジャッジ結果