結果
問題 | No.2479 Sum of Squares |
ユーザー |
|
提出日時 | 2023-09-28 23:07:54 |
言語 | Fortran (gFortran 14.2.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 13,122 bytes |
コンパイル時間 | 2,293 ms |
コンパイル使用メモリ | 37,192 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-21 17:51:20 |
合計ジャッジ時間 | 3,404 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
module unwrapped_vector_muse, intrinsic :: iso_fortran_envimplicit noneprivatepublic :: unwrapped_vector_int32type :: unwrapped_vector_int32privateinteger(int32), allocatable, public :: arr_(:)integer(int32) :: size_ = 0, capa_ = 0containsprocedure, pass :: init => init_unwrapped_vector_int32procedure, pass :: push_back_unwrapped_vector_int32, push_back_array_unwrapped_vector_int32generic :: push_back => push_back_unwrapped_vector_int32, push_back_array_unwrapped_vector_int32procedure, pass :: pop_back => pop_back_unwrapped_vector_int32procedure, pass :: back => back_unwrapped_vector_int32procedure, pass :: size => size_unwrapped_vector_int32procedure, pass :: resize => resize_unwrapped_vector_int32procedure, pass :: lower_bound => lower_bound_unwrapped_vector_int32end type unwrapped_vector_int32interface unwrapped_vector_int32module procedure :: construct_unwrapped_vector_int32_by_size, &construct_unwrapped_vector_int32_by_arr, &construct_unwrapped_vector_int32_by_init_valend interface unwrapped_vector_int32public :: unwrapped_vector_int64type :: unwrapped_vector_int64privateinteger(int64), allocatable, public :: arr_(:)integer(int32) :: size_ = 0, capa_ = 0containsprocedure, pass :: init => init_unwrapped_vector_int64procedure, pass :: push_back_unwrapped_vector_int64, push_back_array_unwrapped_vector_int64generic :: push_back => push_back_unwrapped_vector_int64, push_back_array_unwrapped_vector_int64procedure, pass :: pop_back => pop_back_unwrapped_vector_int64procedure, pass :: back => back_unwrapped_vector_int64procedure, pass :: size => size_unwrapped_vector_int64procedure, pass :: resize => resize_unwrapped_vector_int64procedure, pass :: lower_bound => lower_bound_unwrapped_vector_int64end type unwrapped_vector_int64interface unwrapped_vector_int64module procedure :: construct_unwrapped_vector_int64_by_size, &construct_unwrapped_vector_int64_by_arr, &construct_unwrapped_vector_int64_by_init_valend interface unwrapped_vector_int64contains!> construct_unwrapped_vector_int32_by_size: Construct unwrapped_vector_int32 by the size, the initial values is unknown.impure function construct_unwrapped_vector_int32_by_size(size) result(res)type(unwrapped_vector_int32) :: resinteger(int32), intent(in) :: sizecall res%init(size)end function construct_unwrapped_vector_int32_by_size!> construct_unwrapped_vector_int32_by_arr: Construct unwrapped_vector_int32 by the array of integer(int32).impure function construct_unwrapped_vector_int32_by_arr(arr) result(res)type(unwrapped_vector_int32) :: resinteger(int32), intent(in) :: arr(:)integer(int32) :: nn = size(arr)call res%init(n)res%arr_(1:n) = arr(1:n)end function construct_unwrapped_vector_int32_by_arr!> construct_unwrapped_vector_int32_by_init_val: Construct unwrapped_vector_int32 by size and the initial values.impure function construct_unwrapped_vector_int32_by_init_val(size, val) result(res)type(unwrapped_vector_int32) :: resinteger(int32), intent(in) :: sizeinteger(int32), intent(in) :: valcall res%init(size)res%arr_(1:size) = valend function construct_unwrapped_vector_int32_by_init_val!> init_unwrapped_vector_int32: Initialize the unwrapped_vector_int32 by size.subroutine init_unwrapped_vector_int32(this, n)class(unwrapped_vector_int32), intent(inout) :: thisinteger(int32), intent(in) :: nif (.not. allocated(this%arr_)) thenallocate(this%arr_(n))this%size_ = nthis%capa_ = nend ifend subroutine init_unwrapped_vector_int32!> push_back_unwrapped_vector_int32: Insert value to the tail of elements of the unwrapped_vector_int32.subroutine push_back_unwrapped_vector_int32(this, val)class(unwrapped_vector_int32), intent(inout) :: thisinteger(int32), intent(in) :: valif (.not. allocated(this%arr_)) call this%resize(0)if (this%size_ == this%capa_) thencall this%resize(2*this%capa_)end ifthis%size_ = this%size_ + 1this%arr_(this%size_) = valend subroutine push_back_unwrapped_vector_int32!> push_back_array_unwrapped_vector_int32: Insert elemeents of array to the tail of elements of the unwrapped_vector_int32.subroutine push_back_array_unwrapped_vector_int32(this, arr)class(unwrapped_vector_int32), intent(inout) :: thisinteger(int32), intent(in) :: arr(:)integer(int32) :: ss = size(arr)if (.not. allocated(this%arr_)) call this%init(s)if (this%size_ + s > this%capa_) thencall this%resize(this%size_ + s)end ifthis%arr_(this%size_+1:this%size_+s) = arr(:)this%size_ = this%size_ + send subroutine push_back_array_unwrapped_vector_int32!> pop_back_unwrapped_vector_int32: Delete the value in the end of arr_(:) of the unwrapped_vector_int32 and return it.integer(int32) function pop_back_unwrapped_vector_int32(this)class(unwrapped_vector_int32), intent(inout) :: thispop_back_unwrapped_vector_int32 = this%arr_(this%size_)this%size_ = this%size_ - 1end function pop_back_unwrapped_vector_int32!> back_unwrapped_vector_int32: Delete the value in the end of arr_(:) of the unwrapped_vector_int32 and return it.integer(int32) function back_unwrapped_vector_int32(this)class(unwrapped_vector_int32), intent(inout) :: thisback_unwrapped_vector_int32 = this%arr_(this%size_)end function back_unwrapped_vector_int32!> size_vector_int32: Return current size of the unwrapped_vector_int32.pure integer(int32) function size_unwrapped_vector_int32(this)class(unwrapped_vector_int32), intent(in) :: thissize_unwrapped_vector_int32 = this%size_end function size_unwrapped_vector_int32!> resize_unwrapped_vector_int32: Shrink or expand arr_(:) of the unwrapped_vector_int32.subroutine resize_unwrapped_vector_int32(this, resize)class(unwrapped_vector_int32), intent(inout) :: thisinteger(int32), intent(in) :: resizeinteger(int32), allocatable :: tmp(:)if (resize < 1) thenthis%size_ = 0allocate(tmp(1))call move_alloc(from = tmp, to = this%arr_)this%capa_ = 1elseif (this%capa_ == resize) returnallocate(tmp(resize))this%size_ = min(this%size_, resize)tmp(1:this%size_) = this%arr_(1:this%size_)call move_alloc(from = tmp, to = this%arr_)this%capa_ = resizeend ifend subroutine resize_unwrapped_vector_int32!> lower_bound_vector_int32: Return the minimum index that is higher than or equal to .integer(int32) function lower_bound_unwrapped_vector_int32(this, val)class(unwrapped_vector_int32), intent(in) :: thisinteger(int32), intent(in) :: valinteger(int32) :: p, q, rp = 1r = this%size_if (this%arr_(r) < val) thenlower_bound_unwrapped_vector_int32 = r + 1returnend ifdoq = (p+r)/2if (p + 1 > r) exitif (this%arr_(q) >= val) thenr = qelsep = q+1end ifend dolower_bound_unwrapped_vector_int32 = qend function lower_bound_unwrapped_vector_int32!> construct_unwrapped_vector_int64_by_size: Construct unwrapped_vector_int64 by the size, the initial values is unknown.impure function construct_unwrapped_vector_int64_by_size(size) result(res)type(unwrapped_vector_int64) :: resinteger(int32), intent(in) :: sizecall res%init(size)end function construct_unwrapped_vector_int64_by_size!> construct_unwrapped_vector_int64_by_arr: Construct unwrapped_vector_int64 by the array of integer(int64).impure function construct_unwrapped_vector_int64_by_arr(arr) result(res)type(unwrapped_vector_int64) :: resinteger(int64), intent(in) :: arr(:)integer(int32) :: nn = size(arr)call res%init(n)res%arr_(1:n) = arr(1:n)end function construct_unwrapped_vector_int64_by_arr!> construct_unwrapped_vector_int64_by_init_val: Construct unwrapped_vector_int64 by size and the initial values.impure function construct_unwrapped_vector_int64_by_init_val(size, val) result(res)type(unwrapped_vector_int64) :: resinteger(int32), intent(in) :: sizeinteger(int64), intent(in) :: valcall res%init(size)res%arr_(1:size) = valend function construct_unwrapped_vector_int64_by_init_val!> init_unwrapped_vector_int64: Initialize the unwrapped_vector_int64 by size.subroutine init_unwrapped_vector_int64(this, n)class(unwrapped_vector_int64), intent(inout) :: thisinteger(int32), intent(in) :: nif (.not. allocated(this%arr_)) thenallocate(this%arr_(n))this%size_ = nthis%capa_ = nend ifend subroutine init_unwrapped_vector_int64!> push_back_unwrapped_vector_int64: Insert value to the tail of elements of the unwrapped_vector_int64.subroutine push_back_unwrapped_vector_int64(this, val)class(unwrapped_vector_int64), intent(inout) :: thisinteger(int64), intent(in) :: valif (.not. allocated(this%arr_)) call this%resize(0)if (this%size_ == this%capa_) thencall this%resize(2*this%capa_)end ifthis%size_ = this%size_ + 1this%arr_(this%size_) = valend subroutine push_back_unwrapped_vector_int64!> push_back_array_unwrapped_vector_int64: Insert elemeents of array to the tail of elements of the unwrapped_vector_int64.subroutine push_back_array_unwrapped_vector_int64(this, arr)class(unwrapped_vector_int64), intent(inout) :: thisinteger(int64), intent(in) :: arr(:)integer(int32) :: ss = size(arr)if (.not. allocated(this%arr_)) call this%init(s)if (this%size_ + s > this%capa_) thencall this%resize(this%size_ + s)end ifthis%arr_(this%size_+1:this%size_+s) = arr(:)this%size_ = this%size_ + send subroutine push_back_array_unwrapped_vector_int64!> pop_back_unwrapped_vector_int64: Delete the value in the end of arr_(:) of the unwrapped_vector_int64 and return it.integer(int64) function pop_back_unwrapped_vector_int64(this)class(unwrapped_vector_int64), intent(inout) :: thispop_back_unwrapped_vector_int64 = this%arr_(this%size_)this%size_ = this%size_ - 1end function pop_back_unwrapped_vector_int64!> back_unwrapped_vector_int64: Delete the value in the end of arr_(:) of the unwrapped_vector_int64 and return it.integer(int64) function back_unwrapped_vector_int64(this)class(unwrapped_vector_int64), intent(inout) :: thisback_unwrapped_vector_int64 = this%arr_(this%size_)end function back_unwrapped_vector_int64!> size_vector_int64: Return current size of the unwrapped_vector_int64.pure integer(int32) function size_unwrapped_vector_int64(this)class(unwrapped_vector_int64), intent(in) :: thissize_unwrapped_vector_int64 = this%size_end function size_unwrapped_vector_int64!> resize_unwrapped_vector_int64: Shrink or expand arr_(:) of the unwrapped_vector_int64.subroutine resize_unwrapped_vector_int64(this, resize)class(unwrapped_vector_int64), intent(inout) :: thisinteger(int32), intent(in) :: resizeinteger(int64), allocatable :: tmp(:)if (resize < 1) thenthis%size_ = 0allocate(tmp(1))call move_alloc(from = tmp, to = this%arr_)this%capa_ = 1elseif (this%capa_ == resize) returnallocate(tmp(resize))this%size_ = min(this%size_, resize)tmp(1:this%size_) = this%arr_(1:this%size_)call move_alloc(from = tmp, to = this%arr_)this%capa_ = resizeend ifend subroutine resize_unwrapped_vector_int64!> lower_bound_vector_int64: Return the minimum index that is higher than or equal to .integer(int32) function lower_bound_unwrapped_vector_int64(this, val)class(unwrapped_vector_int64), intent(in) :: thisinteger(int64), intent(in) :: valinteger(int32) :: p, q, rp = 1r = this%size_if (this%arr_(r) < val) thenlower_bound_unwrapped_vector_int64 = r + 1returnend ifdoq = (p+r)/2if (p + 1 > r) exitif (this%arr_(q) >= val) thenr = qelsep = q+1end ifend dolower_bound_unwrapped_vector_int64 = qend function lower_bound_unwrapped_vector_int64end module unwrapped_vector_mprogram yukicoder_2479use, intrinsic :: iso_fortran_envuse unwrapped_vector_m, only: vec_i64 => unwrapped_vector_int64implicit noneinteger(int64) :: s, srtype(vec_i64) :: ansinteger(int64) :: iread(input_unit, *) sdo while (s > 0_int64)sr = floor(sqrt(real(s, real64)), int64)if (sr ** 2 > s) sr = sr - 1call ans%push_back(sr ** 2)s = s - sr ** 2end dowrite(output_unit, '(i0)') ans%size()write(output_unit, '(*(i0, 1x))') ans%arr_(1:ans%size())end program yukicoder_2479