結果
| 問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
| ユーザー |
 sansaqua
|
| 提出日時 | 2021-01-22 22:49:04 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
AC
|
| 実行時間 | 1,616 ms / 2,000 ms |
| コード長 | 10,510 bytes |
| コンパイル時間 | 1,186 ms |
| コンパイル使用メモリ | 61,600 KB |
| 実行使用メモリ | 27,760 KB |
| 最終ジャッジ日時 | 2023-08-27 21:09:21 |
| 合計ジャッジ時間 | 10,459 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 15 ms
25,820 KB |
| testcase_01 | AC | 9 ms
23,728 KB |
| testcase_02 | AC | 9 ms
23,684 KB |
| testcase_03 | AC | 10 ms
23,744 KB |
| testcase_04 | AC | 10 ms
23,684 KB |
| testcase_05 | AC | 11 ms
27,760 KB |
| testcase_06 | AC | 29 ms
27,392 KB |
| testcase_07 | AC | 21 ms
23,860 KB |
| testcase_08 | AC | 23 ms
23,796 KB |
| testcase_09 | AC | 21 ms
23,896 KB |
| testcase_10 | AC | 20 ms
23,804 KB |
| testcase_11 | AC | 1,359 ms
23,860 KB |
| testcase_12 | AC | 1,229 ms
23,864 KB |
| testcase_13 | AC | 1,600 ms
25,860 KB |
| testcase_14 | AC | 1,044 ms
23,864 KB |
| testcase_15 | AC | 1,211 ms
23,820 KB |
| testcase_16 | AC | 1,616 ms
23,808 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 27 AUG 2023 09:09:10 PM): ; processing (IN-PACKAGE :CL-USER) ; processing (DEFPARAMETER *OPT* ...) ; processing (SET-DISPATCH-MACRO-CHARACTER #\# ...) ; processing (SETQ *RANDOM-STATE* ...) ; processing (DEFINE-INT-TYPES 2 ...) ; processing (DEFCONSTANT +MOD+ ...) ; processing (DEFMACRO DBG ...) ; processing (DECLAIM (INLINE PRINTLN)) ; processing (DEFUN PRINTLN ...) ; processing (DEFPACKAGE :CP/EXT-GCD ...) ; processing (IN-PACKAGE :CP/EXT-GCD) ; processing (DECLAIM (FTYPE # ...)) ; processing (DEFUN %EXT-GCD ...) ; processing (DECLAIM (INLINE EXT-GCD)) ; processing (DEFUN EXT-GCD ...) ; processing (DEFPACKAGE :CP/BEZOUT ...) ; processing (IN-PACKAGE :CP/BEZOUT) ; processing (DECLAIM (INLINE %CALC-MIN-FACTOR)) ; processing (DEFUN %CALC-MIN-FACTOR ...) ; processing (DECLAIM (INLINE %CALC-MAX-FACTOR)) ; processing (DEFUN %CALC-MAX-FACTOR ...) ; processing (DECLAIM (INLINE SOLVE-BEZOUT)) ; processing (DEFUN SOLVE-BEZOUT ...) ; file: /home/judge/data/code/Main.lisp ; in: DEFUN SOLVE-BEZOUT ; (CP/BEZOUT:%CALC-MIN-FACTOR (- CP/BEZOUT::X0 MIN) CP/BEZOUT::DELTAX) ; --> BLOCK IF ; ==> ; (FLOOR (- CP/BEZOUT::X) CP/BEZOUT::ALPHA) ; ; note: unable to ; convert integer division to multiplication ; due to type uncertainty: ; The first argument is a (INTEGER -21267647932558653957237540927630737409 ; 21267647932558653961849226948205608959), not a (SIGNED-BYTE ; 64). ; ; note: unable to ; convert integer division to multiplication ; due to type uncertainty: ; The first argument is a (INTEGER -21267647932558653957237540927630737409 ; 21267647932558653961849226948205608959), not a (UNSIGNED-BYTE ; 64). ; (CP/BEZOUT:%CALC-MAX-FACTOR (- CP/BEZOUT::X0 MAX) CP/BEZOUT::DELTAX) ; --> BLOCK IF ; ==> ; (CEIL
ソースコード
(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))))
#+sbcl (setq *random-state* (seed-random-state (nth-value 1 (get-time-of-day)))))
#-swank (eval-when (:compile-toplevel)
(setq *break-on-signals* '(and warning (not style-warning))))
#+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)
(declare (ignorable forms))
#+swank (if (= (length forms) 1)
`(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
`(format *error-output* "~A => ~A~%" ',forms `(,,@forms))))
(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
(let ((*read-default-float-format*
(if (typep obj 'double-float) 'double-float *read-default-float-format*)))
(prog1 (princ obj stream) (terpri stream))))
;; BEGIN_INSERTED_CONTENTS
(defpackage :cp/ext-gcd
(:use :cl)
(:export #:ext-gcd))
(in-package :cp/ext-gcd)
;; Blankinship algorithm
;; Reference: https://topcoder-g-hatena-ne-jp.jag-icpc.org/spaghetti_source/20130126/ (Japanese)
(declaim (ftype (function * (values fixnum fixnum &optional)) %ext-gcd))
(defun %ext-gcd (a b)
(declare (optimize (speed 3) (safety 0))
(fixnum a b))
(let ((y 1)
(x 0)
(u 1)
(v 0))
(declare (fixnum y x u v))
(loop (when (zerop a)
(return (values x y)))
(let ((q (floor b a)))
(decf x (the fixnum (* q u)))
(rotatef x u)
(decf y (the fixnum (* q v)))
(rotatef y v)
(decf b (the fixnum (* q a)))
(rotatef b a)))))
;; TODO: deal with bignums
(declaim (inline ext-gcd))
(defun ext-gcd (a b)
"Returns two integers X and Y which satisfy AX + BY = gcd(A, B)."
(declare ((integer #.(- most-positive-fixnum) #.most-positive-fixnum) a b))
(if (>= a 0)
(if (>= b 0)
(%ext-gcd a b)
(multiple-value-bind (x y) (%ext-gcd a (- b))
(declare (fixnum x y))
(values x (- y))))
(if (>= b 0)
(multiple-value-bind (x y) (%ext-gcd (- a) b)
(declare (fixnum x y))
(values (- x) y))
(multiple-value-bind (x y) (%ext-gcd (- a) (- b))
(declare (fixnum x y))
(values (- x) (- y))))))
(defpackage :cp/bezout
(:use :cl :cp/ext-gcd)
(:export #:solve-bezout #:%calc-min-factor #:%calc-max-factor))
(in-package :cp/bezout)
(declaim (inline %calc-min-factor))
(defun %calc-min-factor (x alpha)
"Returns k, so that x+k*alpha is the smallest non-negative number."
(if (plusp alpha)
(ceiling (- x) alpha)
(floor (- x) alpha)))
(declaim (inline %calc-max-factor))
(defun %calc-max-factor (x alpha)
"Returns k, so that x+k*alpha is the largest non-positive number."
(if (plusp alpha)
(floor (- x) alpha)
(ceiling (- x) alpha)))
(declaim (inline solve-bezout))
(defun solve-bezout (a b c gcd init-x init-y &optional min max)
"Returns an integer solution of a*x+b*y = c if it exists, otherwise
returns (VALUES NIL NIL).
- If MIN is specified and MAX is null, the returned x is the smallest integer
equal to or larger than MIN.
- If MAX is specified and MIN is null, x is the largest integer equal to or
smaller than MAX.
- If both are specified, x is an integer in [MIN, MAX]. This function returns
NIL when there is no x that satisfies the given condition."
(declare (optimize (speed 3))
((unsigned-byte 62) a b c gcd)
((or null (unsigned-byte 31)) min max)
(fixnum init-x init-y))
(let ((gcd-ab gcd))
(if (zerop (mod c gcd-ab))
(let* ((factor (floor c gcd-ab))
;; m*x0 + n*y0 = d
(x0 (* init-x factor))
(y0 (* init-y factor)))
(if (and (null min) (null max))
(values x0 y0)
(let (;; general solution: x = x0 + kΔx, y = y0 - kΔy
(deltax (floor b gcd-ab))
(deltay (floor a gcd-ab)))
(if min
(let* ((k-min (%calc-min-factor (- x0 min) deltax))
(x (+ x0 (* k-min deltax)))
(y (- y0 (* k-min deltay))))
(if (and max (> x max))
(values nil nil)
(values x y)))
(let* ((k-max (%calc-max-factor (- x0 max) deltax))
(x (+ x0 (* k-max deltax)))
(y (- y0 (* k-max deltay))))
(if (<= x max)
(values x y)
(values nil nil)))))))
(values nil nil))))
;;;
;;; Arithmetic operations with static modulus
;;;
(defpackage :cp/mod-operations
(:use :cl)
(:export #:define-mod-operations))
(in-package :cp/mod-operations)
(defmacro define-mod-operations
(divisor &optional (package #+sbcl (sb-int:sane-package) #-sbcl *package*))
(let ((mod* (intern "MOD*" package))
(mod+ (intern "MOD+" package))
(mod- (intern "MOD-" package))
(incfmod (intern "INCFMOD" package))
(decfmod (intern "DECFMOD" package))
(mulfmod (intern "MULFMOD" package)))
`(progn
(defun ,mod* (&rest args)
(cond ((cdr args) (reduce (lambda (x y) (mod (* x y) ,divisor)) args))
(args (mod (car args) ,divisor))
(t 1)))
(defun ,mod+ (&rest args)
(cond ((cdr args) (reduce (lambda (x y) (mod (+ x y) ,divisor)) args))
(args (mod (car args) ,divisor))
(t 0)))
(defun ,mod- (&rest args)
(if (cdr args)
(reduce (lambda (x y) (mod (- x y) ,divisor)) args)
(mod (- (car args)) ,divisor)))
#+sbcl
(eval-when (:compile-toplevel :load-toplevel :execute)
(locally (declare (sb-ext:muffle-conditions warning))
(sb-c:define-source-transform ,mod* (&rest args)
(case (length args)
(0 1)
(1 `(mod ,(car args) ,',divisor))
(otherwise (reduce (lambda (x y) `(mod (* ,x ,y) ,',divisor)) args))))
(sb-c:define-source-transform ,mod+ (&rest args)
(case (length args)
(0 0)
(1 `(mod ,(car args) ,',divisor))
(otherwise (reduce (lambda (x y) `(mod (+ ,x ,y) ,',divisor)) args))))
(sb-c:define-source-transform ,mod- (&rest args)
(case (length args)
(0 (values nil t))
(1 `(mod (- ,(car args)) ,',divisor))
(otherwise (reduce (lambda (x y) `(mod (- ,x ,y) ,',divisor)) args))))))
(define-modify-macro ,incfmod (delta)
(lambda (x y) (mod (+ x y) ,divisor)))
(define-modify-macro ,decfmod (delta)
(lambda (x y) (mod (- x y) ,divisor)))
(define-modify-macro ,mulfmod (multiplier)
(lambda (x y) (mod (* x y) ,divisor))))))
;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
(use-package :cp/mod-operations :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
(use-package :cp/ext-gcd :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
(use-package :cp/bezout :cl-user))
(in-package :cl-user)
;;;
;;; Body
;;;
(define-mod-operations +mod+)
(declaim (inline solve))
(defun solve (a b c)
(declare (optimize (speed 3))
((unsigned-byte 62) a b c))
(let ((gcd-ab (gcd a b)))
(if (zerop (mod c gcd-ab))
(ext-gcd a b)
(values nil nil))))
(defun main ()
(declare #.*opt*)
(let* ((tt (read)))
(dotimes (_ tt)
(destructuring-bind (n k h)
(sort (loop repeat 3 collect (read)) #'>)
(declare (uint31 n k h))
(let ((y (read))
(res 0)
(gcd (gcd k h)))
(declare (uint62 y)
(uint31 res))
(dbg n k h y)
(multiple-value-bind (init-x init-y) (ext-gcd k h)
(loop for base from 0 to y by n
for rest = (- y base)
do ;; (dbg base rest)
(multiple-value-bind (i1 j1)
(solve-bezout k h rest gcd init-x init-y 0 nil)
(when i1
(multiple-value-bind (i2 j2)
(solve-bezout h k rest gcd init-y init-x 0 nil)
(when j2
(when (<= i1 j2)
(let ((d (floor h gcd)))
(declare (uint62 i1 j2))
(assert (zerop (mod (abs (- i1 j2)) d)))
(incfmod res (+ 1 (floor (abs (- i1 j2)) d)))))))))))
(println res))))))
#-swank (main)
;;;
;;; Test
;;;
#+swank
(progn
(defparameter *lisp-file-pathname* (uiop:current-lisp-file-pathname))
(setq *default-pathname-defaults* (uiop:pathname-directory-pathname *lisp-file-pathname*))
(uiop:chdir *default-pathname-defaults*)
(defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *lisp-file-pathname*))
(defparameter *problem-url* "https://yukicoder.me/problems/no/1358"))
#+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)))
#+(and sbcl (not swank))
(eval-when (:compile-toplevel)
(when sb-c::*undefined-warnings*
(error "undefined warnings: ~{~A~^ ~}" sb-c::*undefined-warnings*)))
;; To run: (5am:run! :sample)
#+swank
(5am:test :sample
(5am:is
(equal "3
1
0
30554
"
(run "4
2 3 5 9
4 5 1 1
10 10 10 1
31415 92653 58979 3238462643
" nil))))