#447909 (Common Lisp) No.3 ビットすごろく

提出ソース

結果

問題	No.3 ビットすごろく
ユーザー	sansaqua
提出日時	2020-03-22 07:32:42
言語	Common Lisp (sbcl 2.3.8)
結果	AC
実行時間	11 ms / 5,000 ms
コード長	5,647 bytes
コンパイル時間	1,016 ms
コンパイル使用メモリ	39,804 KB
実行使用メモリ	22,912 KB
最終ジャッジ日時	2024-07-01 09:42:14
合計ジャッジ時間	2,278 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	10 ms 22,528 KB
testcase_01	AC	10 ms 22,528 KB
testcase_02	AC	10 ms 22,528 KB
testcase_03	AC	9 ms 22,656 KB
testcase_04	AC	10 ms 22,528 KB
testcase_05	AC	10 ms 22,656 KB
testcase_06	AC	10 ms 22,656 KB
testcase_07	AC	9 ms 22,784 KB
testcase_08	AC	11 ms 22,656 KB
testcase_09	AC	10 ms 22,656 KB
testcase_10	AC	10 ms 22,784 KB
testcase_11	AC	11 ms 22,656 KB
testcase_12	AC	10 ms 22,656 KB
testcase_13	AC	10 ms 22,656 KB
testcase_14	AC	10 ms 22,656 KB
testcase_15	AC	11 ms 22,656 KB
testcase_16	AC	11 ms 22,912 KB
testcase_17	AC	10 ms 22,656 KB
testcase_18	AC	10 ms 22,656 KB
testcase_19	AC	10 ms 22,784 KB
testcase_20	AC	10 ms 22,528 KB
testcase_21	AC	10 ms 22,400 KB
testcase_22	AC	10 ms 22,656 KB
testcase_23	AC	9 ms 22,784 KB
testcase_24	AC	10 ms 22,784 KB
testcase_25	AC	10 ms 22,784 KB
testcase_26	AC	10 ms 22,528 KB
testcase_27	AC	10 ms 22,784 KB
testcase_28	AC	10 ms 22,656 KB
testcase_29	AC	9 ms 22,656 KB
testcase_30	AC	10 ms 22,528 KB
testcase_31	AC	10 ms 22,656 KB
testcase_32	AC	10 ms 22,656 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

; compiling file "/home/judge/data/code/Main.lisp" (written 01 JUL 2024 09:42:12 AM):

; wrote /home/judge/data/code/Main.fasl
; compilation finished in 0:00:00.058

ソースコード

raw source code

(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           ;; enclose the form with VALUES to avoid being captured by LOOP macro
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
;;;
;;; Queue with singly linked list
;;;

(defstruct (queue (:constructor make-queue
                      (&optional list &aux (tail (last list)))))
  (list nil :type list)
  (tail nil :type list))

(declaim (inline enqueue))
(defun enqueue (obj queue)
  "Pushes OBJ to the end of QUEUE."
  (symbol-macrolet ((list (queue-list queue))
                    (tail (queue-tail queue)))
    (if (null list)
        (setf tail (list obj)
              list tail)
        (setf (cdr tail) (list obj)
              tail (cdr tail))))
  queue)

(declaim (inline dequeue))
(defun dequeue (queue)
  "Removes and returns the element at the front of QUEUE. Returns NIL if QUEUE
is empty."
  (pop (queue-list queue)))

(declaim (inline queue-empty-p))
(defun queue-empty-p (queue)
  (null (queue-list queue)))

(declaim (inline queue-peek))
(defun queue-peek (queue)
  (car (queue-list queue)))

(declaim (inline enqueue-front))
(defun enqueue-front (obj queue)
  "Pushes OBJ to the front of QUEUE."
  (symbol-macrolet ((list (queue-list queue))
                    (tail (queue-tail queue)))
    (if (null list)
        (setf tail (list obj)
              list tail)
        (push obj list))
    queue))

(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)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(defconstant +inf+ #xffffffff)
(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (dists (make-array (+ n 1) :element-type 'uint32 :initial-element +inf+))
         (que (make-queue)))
    (declare (uint32 n))
    (setf (aref dists 1) 1)
    (enqueue 1 que)
    (loop until (queue-empty-p que)
          for v of-type uint32 = (dequeue que)
          for delta = (logcount v)
          when (and (<= (+ v delta) n)
                    (= (aref dists (+ v delta)) +inf+))
          do (setf (aref dists (+ v delta)) (+ (aref dists v) 1))
             (enqueue (+ v delta) que)
          when (and (>= (- v delta) 1)
                    (= (aref dists (- v delta)) +inf+))
          do (setf (aref dists (- v delta)) (+ (aref dists v) 1))
             (enqueue (- v delta) que))
    (println
     (if (= (aref dists n) +inf+)
         -1
         (aref dists n)))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (ensure-last-lf out-string)
             (with-output-to-string (out)
               (let ((*standard-output* out))
                 (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                   (funcall function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let ((*standard-output* out))
    (etypecase thing
      (null
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "5
"
    "4
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "11
"
    "9
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "4
"
    "-1
")))

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード