結果
| 問題 | No.979 Longest Divisor Sequence |
| ユーザー |
 sansaqua
|
| 提出日時 | 2020-01-31 22:14:20 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
AC
|
| 実行時間 | 673 ms / 2,000 ms |
| コード長 | 8,934 bytes |
| コンパイル時間 | 312 ms |
| コンパイル使用メモリ | 42,496 KB |
| 実行使用メモリ | 123,520 KB |
| 最終ジャッジ日時 | 2024-09-17 08:33:37 |
| 合計ジャッジ時間 | 6,983 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge6 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 336 ms
123,264 KB |
| testcase_01 | AC | 324 ms
123,136 KB |
| testcase_02 | AC | 327 ms
123,392 KB |
| testcase_03 | AC | 323 ms
123,392 KB |
| testcase_04 | AC | 322 ms
123,264 KB |
| testcase_05 | AC | 321 ms
123,392 KB |
| testcase_06 | AC | 318 ms
123,392 KB |
| testcase_07 | AC | 323 ms
123,392 KB |
| testcase_08 | AC | 320 ms
123,392 KB |
| testcase_09 | AC | 325 ms
123,264 KB |
| testcase_10 | AC | 328 ms
123,392 KB |
| testcase_11 | AC | 325 ms
123,392 KB |
| testcase_12 | AC | 327 ms
123,392 KB |
| testcase_13 | AC | 331 ms
123,264 KB |
| testcase_14 | AC | 673 ms
123,520 KB |
| testcase_15 | AC | 399 ms
123,520 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 17 SEP 2024 08:33:22 AM): ; file: /home/judge/data/code/Main.lisp ; in: DEFUN MAKE-DIVISORS-TABLE ; (MAKE-ARRAY SUP :ELEMENT-TYPE 'LIST) ; ; caught STYLE-WARNING: ; The default initial element 0 is not a LIST. ; See also: ; The ANSI Standard, Function MAKE-ARRAY ; The ANSI Standard, Function UPGRADED-ARRAY-ELEMENT-TYPE ; ; caught STYLE-WARNING: ; The default initial element 0 is not a LIST. ; See also: ; The ANSI Standard, Function MAKE-ARRAY ; The ANSI Standard, Function UPGRADED-ARRAY-ELEMENT-TYPE ; ; compilation unit finished ; caught 2 STYLE-WARNING conditions ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.072
ソースコード
(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
(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))
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
"NOTE: cannot read -2^62"
(declare #.OPT)
(macrolet ((%read-byte ()
`(the (unsigned-byte 8)
#+swank (char-code (read-char in nil #\Nul))
#-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
(let* ((minus nil)
(result (loop (let ((byte (%read-byte)))
(cond ((<= 48 byte 57)
(return (- byte 48)))
((zerop byte) ; #\Nul
(error "Read EOF or #\Nul."))
((= byte #.(char-code #\-))
(setf minus t)))))))
(declare ((integer 0 #.most-positive-fixnum) result))
(loop
(let* ((byte (%read-byte)))
(if (<= 48 byte 57)
(setq result (+ (- byte 48)
(* 10 (the (integer 0 #.(floor most-positive-fixnum 10))
result))))
(return (if minus (- result) result))))))))
(declaim (ftype (function * (values (vector (integer 0 #.most-positive-fixnum)) &optional))
enum-divisors))
(defun enum-divisors (x)
"Enumerates all the divisors of X in O(sqrt(X)). Note that the resultant
vector is NOT sorted."
(declare (optimize (speed 3))
((integer 0 #.most-positive-fixnum) x))
(let* ((sqrt (isqrt x))
(res (make-array (isqrt sqrt) ; FIXME: sets the initial size to x^1/4
:element-type '(integer 0 #.most-positive-fixnum)
:fill-pointer 0)))
(loop for i from 1 to sqrt
do (multiple-value-bind (quot rem) (floor x i)
(when (zerop rem)
(vector-push-extend i res)
(unless (= i quot)
(vector-push-extend quot res)))))
res))
;; Below is the variant that returns a sorted list.
(defun enum-ascending-divisors (n)
"Returns the increasing list of all the divisors of N."
(declare (optimize (speed 3))
((integer 1 #.most-positive-fixnum) n))
(if (= n 1)
(list 1)
(let* ((sqrt (isqrt n))
(result (list 1)))
(labels ((%enum (i first-half second-half)
(declare ((integer 1 #.most-positive-fixnum) i))
(cond ((or (< i sqrt)
(and (= i sqrt) (/= (* sqrt sqrt) n)))
(multiple-value-bind (quot rem) (floor n i)
(if (zerop rem)
(progn
(setf (cdr first-half) (list i))
(setf second-half (cons quot second-half))
(%enum (1+ i) (cdr first-half) second-half))
(%enum (1+ i) first-half second-half))))
((= i sqrt) ; N is a square number here
(setf (cdr first-half) (cons i second-half)))
(t ; (> i sqrt)
(setf (cdr first-half) second-half)))))
(%enum 2 result (list n))
result))))
(declaim (ftype (function * (values (simple-array list (*)) &optional)) make-divisors-table))
(defun make-divisors-table (sup)
"Returns a vector of length SUP whose each cell, vector[INDEX], is the
increasing list of every divisor of INDEX. Note that vector[0] = NIL."
(declare #.OPT
((integer 0 #.most-positive-fixnum) sup))
(let ((result (make-array sup :element-type 'list))
(tails (make-array sup :element-type 'list))) ; preserves the last cons
(declare (optimize (speed 3) (safety 0)))
(loop for i from 1 below sup
for cell = (list 1)
do (setf (aref result i) cell
(aref tails i) cell))
(when (>= sup 1)
(setf (aref result 0) nil))
(loop for divisor from 2 below sup
do (loop for number from divisor below sup by divisor
do (setf (cdr (aref tails number)) (list divisor))
(setf (aref tails number) (cdr (aref tails number)))))
result))
(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
;;;
(defun main ()
(declare #.OPT)
(let* ((n (read))
(div-table (make-divisors-table 300001))
(pos-table (make-array 300001 :element-type 'list :initial-element nil))
(as (make-array n :element-type 'uint31))
(dp (make-array n :element-type 'uint31 :initial-element 1)))
(dotimes (i n)
(setf (aref as i) (read-fixnum))
(push i (aref pos-table (aref as i))))
(loop for x from (- n 1) above 0
for a = (aref as x)
do (dolist (div (aref div-table a))
(declare (uint31 div))
(unless (= div a)
(let ((poses (aref pos-table div)))
(loop (unless poses (return))
(let ((pos (car poses)))
(declare (uint31 pos))
(when (< pos x) (return))
(pop poses)))
(when poses
(let ((prev-pos (car poses)))
(maxf (aref dp prev-pos)
(+ 1 (aref dp x)))))))))
#>dp
(println (reduce #'max dp))))
#-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)))