Submission #6244246

---

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

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

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

(defconstant +mod+ 1000000007)

;; Body
(defun calc-order (k)
  (let* ((power10-table (make-array k :element-type 'bit :initial-element 0)))
    (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))
    (count 1 power10-table)))

(defun main ()
  (declare #.OPT)
  (let* ((k (read))
         (queue (make-queue))
         (power10-table (make-array k :element-type 'bit :initial-element 0))
         (dist-table (make-array k :element-type 'uint32 :initial-element #xffffffff)))
    (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))
      (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)
                 (let ((dest (mod (+ delta x) k)))
                   (when (zerop dest)
                     (println (+ 1 (aref dist-table x)))
                     (return-from main))
                   (when (= #xffffffff (aref dist-table dest))
                     (setf (aref dist-table dest)
                           (+ 1 (aref dist-table x)))
                     (enqueue dest queue))))))))

#-swank(main)

Submission Info

Judge Result