Submission #6251699

---

Source Code Expand

;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
;; -*- coding:utf-8 -*-
(defstruct (queue (:constructor make-queue
                    (&optional list &aux (tail (last list)))))
  (list nil :type list)
  (tail nil :type (or null (cons t null))))

(declaim (inline enqueue))
(defun enqueue (obj 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)
  (pop (queue-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)

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

(defconstant +mod+ 1000000007)

;; Body
(defun main ()
  (declare #.OPT)
  (sb-int:with-progressive-timeout (remaining-time :seconds 1.92)
    (let* ((k (read))
           (queue (make-queue))
           (power10-table (make-array k :element-type 'bit :initial-element 0))
           (dist-table (make-array k :element-type 'uint8 :initial-element #xff)))
      (declare (uint32 k))
      (loop for x = 1 then (mod (* x 10) k)
            until (= 1 (aref power10-table x))
            do (setf (aref power10-table x) 1
                     (aref dist-table x) 1)
               (enqueue x queue)
               (when (zerop x)
                 (println 1)
                 (return-from main)))
      (let ((delta-vec (make-array (count 1 power10-table) :element-type 'uint32))
            (index 0)
            (counter 0))
        (declare (uint32 counter))
        (dotimes (x k)
          (when (= 1 (aref power10-table x))
            (setf (aref delta-vec index) x)
            (incf index)))
        (loop for x of-type uint32 = (dequeue queue)
              do (sb-int:dovector (delta delta-vec)
                   (incf counter)
                   (let ((dest (mod (+ delta x) k)))
                     (when (zerop dest)
                       (println (+ 1 (aref dist-table x)))
                       (return-from main))
                     (when (= #xff (aref dist-table dest))
                       (setf (aref dist-table dest)
                             (+ 1 (aref dist-table x)))
                       (enqueue dest queue))))
                 (when (>= counter 100000)
                   (setq counter 0)
                   (when (zerop (remaining-time))
                     (println 3)
                     (return-from main))))))))

#-swank(main)

Submission Info

Judge Result