結果
| 問題 | No.21 平均の差 |
| ユーザー |
 sansaqua
|
| 提出日時 | 2020-10-27 03:44:34 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
AC
|
| 実行時間 | 522 ms / 5,000 ms |
| コード長 | 4,282 bytes |
| コンパイル時間 | 198 ms |
| コンパイル使用メモリ | 38,528 KB |
| 実行使用メモリ | 60,800 KB |
| 最終ジャッジ日時 | 2024-07-21 21:49:35 |
| 合計ジャッジ時間 | 1,785 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 9 ms
22,400 KB |
| testcase_01 | AC | 17 ms
24,320 KB |
| testcase_02 | AC | 45 ms
31,744 KB |
| testcase_03 | AC | 8 ms
22,400 KB |
| testcase_04 | AC | 522 ms
22,528 KB |
| testcase_05 | AC | 9 ms
22,272 KB |
| testcase_06 | AC | 9 ms
22,400 KB |
| testcase_07 | AC | 11 ms
22,656 KB |
| testcase_08 | AC | 11 ms
22,528 KB |
| testcase_09 | AC | 280 ms
60,800 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 21 JUL 2024 09:49:33 PM): ; file: /home/judge/data/code/Main.lisp ; in: DEFUN MAIN ; (LOOP FOR ; SUM ACROSS SUMS ; FOR ; COUNT ACROSS COUNTS ; MAXIMIZE (/ SUM COUNT) INTO ...) ; --> LET LET LET LET SB-LOOP::WITH-MINIMAX-VALUE LET ; --> SB-LOOP::WITH-MINIMAX-VALUE LET TAGBODY ; --> SB-LOOP::LOOP-ACCUMULATE-MINIMAX-VALUE PROGN WHEN IF OR LET IF > IF ; ==> ; (> #:LOOP-MAXMIN-TEMP-8 MAX) ; ; note: forced to do GENERIC-> (cost 10) ; unable to do inline fixnum comparison (cost 4) because: ; The first argument is a (RATIONAL 0 2147483647), not a FIXNUM. ; The second argument is a (RATIONAL 0 2147483647), not a FIXNUM. ; --> LET LET LET LET SB-LOOP::WITH-MINIMAX-VALUE LET ; --> SB-LOOP::WITH-MINIMAX-VALUE LET TAGBODY ; --> SB-LOOP::LOOP-ACCUMULATE-MINIMAX-VALUE PROGN WHEN IF OR LET IF < IF ; ==> ; (< #:LOOP-MAXMIN-TEMP-10 MIN) ; ; note: forced to do GENERIC-< (cost 10) ; unable to do inline fixnum comparison (cost 4) because: ; The first argument is a (RATIONAL 0 2147483647), not a FIXNUM. ; The second argument is a (RATIONAL 0 2147483647), not a FIXNUM. ; (- MAX MIN) ; ; note: forced to do GENERIC-- (cost 10) ; unable to do inline fixnum arithmetic (cost 2) because: ; The first argument is a (RATIONAL 0 2147483647), not a FIXNUM. ; The second argument is a (RATIONAL 0 2147483647), not a FIXNUM. ; The result is a (VALUES (RATIONAL -2147483647 2147483647) &OPTIONAL), not a (VALUES ; FIXNUM ; &OPTIONAL). ; unable to do inline (unsigned-byte 64) arithmetic (cost 4) because: ; The first argument is a (RATIONAL 0 2147483647), not a (UNSIGNED-BYTE 64). ; The second argument is a (RATIONAL 0 2147483647), not a (UNSIGNED
ソースコード
(in-package :cl-user)
(eval-when (:compile-toplevel :load-toplevel :execute)
(defparameter *opt*
#+swank '(optimize (speed 3) (safety 2))
#-swank '(optimize (speed 3) (safety 0) (debug 0)))
#+swank (ql:quickload '(:cl-debug-print :fiveam :cp/util) :silent t)
#+swank (use-package :cp/util :cl-user)
#-swank (set-dispatch-macro-character
#\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (set-dispatch-macro-character #\# #\> #'cl-debug-print:debug-print-reader)
(macrolet ((def (b)
`(progn (deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))
(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))))
(define-int-types (&rest bits) `(progn ,@(mapcar (lambda (b) `(def ,b)) bits))))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64))
(defconstant +mod+ 1000000007)
(defmacro dbg (&rest forms)
#+swank (if (= (length forms) 1)
`(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
`(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
#-swank (declare (ignore forms)))
(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
(let ((*read-default-float-format* 'double-float))
(prog1 (princ obj stream) (terpri stream))))
;; BEGIN_INSERTED_CONTENTS
(defpackage :cp/modify-macro
(:use :cl)
(:export #:minf #:maxf #:mulf #:divf #:iorf #:xorf #:andf))
(in-package :cp/modify-macro)
(macrolet ((def (name fname)
`(define-modify-macro ,name (new-value) ,fname)))
(def minf min)
(def maxf max)
(def mulf *)
(def divf /)
(def iorf logior)
(def xorf logxor)
(def andf logand))
;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
(use-package :cp/modify-macro :cl-user))
(in-package :cl-user)
;;;
;;; Body
;;;
(defun main ()
(declare #.*opt*)
(let* ((n (read))
(k (read))
(nums (coerce (loop repeat n collect (read)) '(simple-array uint31 (*))))
(state (make-array n :element-type 'uint8 :initial-element 0))
(sums (make-array k :element-type 'uint31 :initial-element 0))
(counts (make-array k :element-type 'uint31 :initial-element 0))
(res 0))
(declare (uint4 n k))
(setf (aref sums 0) (aref nums 0)
(aref counts 0) 1)
(labels ((update! ()
(unless (find 0 counts)
(loop for sum across sums
for count across counts
maximize (/ sum count) into max
minimize (/ sum count) into min
do (maxf res (round (- max min))))))
(dfs (pos)
(if (= pos n)
(update!)
(dotimes (i k)
(setf (aref state pos) i)
(incf (aref sums i) (aref nums pos))
(incf (aref counts i))
(dfs (+ pos 1))
(decf (aref sums i) (aref nums pos))
(decf (aref counts i))))))
(dfs 1)
(println res))))
#-swank (main)
;;;
;;; Test and benchmark
;;;
#+swank
(progn
(defparameter *lisp-file-pathname* (uiop:current-lisp-file-pathname))
(setq *default-pathname-defaults* (uiop:pathname-directory-pathname *lisp-file-pathname*))
(defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *lisp-file-pathname*))
(defparameter *problem-url* "https://yukicoder.me/problems/no/21"))
#+swank
(defun gen-dat ()
(uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
(format out "9 9~%")
(dotimes (_ 9)
(println (+ 1 (random 1000)) out))))
#+swank
(defun bench (&optional (out (make-broadcast-stream)))
(time (run *dat-pathname* out)))
#-swank
(eval-when (:compile-toplevel)
(when (or (> sb-c::*compiler-warning-count* 0)
sb-c::*undefined-warnings*)
(error "count: ~D, undefined warnings: ~A"
sb-c::*compiler-warning-count*
sb-c::*undefined-warnings*)))
;; To run: (5am:run! :sample)
#+swank
(5am:test :sample
(5am:is
(equal "535
"
(run "5
3
555
20
432
301
21
" nil)))
(5am:is
(equal "651
"
(run "8
4
329
980
656
738
739
542
873
501
" nil))))