結果
| 問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
| ユーザー |
 sansaqua
|
| 提出日時 | 2021-01-22 22:45:01 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,750 bytes |
| コンパイル時間 | 1,043 ms |
| コンパイル使用メモリ | 48,512 KB |
| 実行使用メモリ | 28,544 KB |
| 最終ジャッジ日時 | 2024-06-08 16:33:51 |
| 合計ジャッジ時間 | 5,097 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 30 ms
28,544 KB |
| testcase_01 | AC | 9 ms
23,040 KB |
| testcase_02 | AC | 9 ms
22,912 KB |
| testcase_03 | AC | 8 ms
23,040 KB |
| testcase_04 | AC | 8 ms
23,040 KB |
| testcase_05 | AC | 8 ms
23,040 KB |
| testcase_06 | AC | 66 ms
23,168 KB |
| testcase_07 | AC | 47 ms
23,040 KB |
| testcase_08 | AC | 50 ms
23,168 KB |
| testcase_09 | AC | 46 ms
23,040 KB |
| testcase_10 | AC | 39 ms
23,168 KB |
| testcase_11 | TLE | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 08 JUN 2024 04:33:45 PM): ; file: /home/judge/data/code/Main.lisp ; in: DEFUN SOLVE-BEZOUT ; (GCD CP/BEZOUT::A CP/BEZOUT::B) ; ; note: unable to ; optimize ; due to type uncertainty: ; The first argument is a (UNSIGNED-BYTE 62), not a (OR ; (INTEGER ; -4611686018427387904 -1) ; (INTEGER 1 ; 4611686018427387903)). ; The second argument is a (UNSIGNED-BYTE 62), not a (OR ; (INTEGER ; -4611686018427387904 -1) ; (INTEGER 1 ; 4611686018427387903)). ; (* CP/BEZOUT::INIT-X CP/BEZOUT::FACTOR) ; ; note: forced to do */SIGNED=>INTEGER (cost 10) ; unable to do inline fixnum arithmetic (cost 2) because: ; The result is a (VALUES ; (INTEGER -21267647932558653961849226946058125312 ; 21267647932558653957237540927630737409) ; &OPTIONAL), not a (VALUES FIXNUM &OPTIONAL). ; unable to do inline (signed-byte 64) arithmetic (cost 4) because: ; The result is a (VALUES ; (INTEGER -21267647932558653961849226946058125312 ; 21267647932558653957237540927630737409) ; &OPTIONAL), not a (VALUES (SIGNED-BYTE 64) &OPTIONAL). ; (* CP/BEZOUT::INIT-Y CP/BEZOUT::FACTOR) ; ; note: forced to do */SIGNED=>INTEGER (cost 10) ; unable to do inline fixnum arithmetic (cost 2) because: ; The result is a (VALUES ; (INTEGER -21267647932558653961849226946058125312 ; 2126764793255865395723
ソースコード
(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)))
(defun solve-bezout (a b c &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)
((or null (unsigned-byte 31)) min max))
(let ((gcd-ab (gcd a b)))
(if (zerop (mod c gcd-ab))
(multiple-value-bind (init-x init-y) (ext-gcd a b)
(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)
(labels ((%solve (a b c init-x init-y min max)
(let* ((factor (floor c gcd))
;; 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))
(deltay (floor a gcd)))
(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)))))))))
(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 0 nil)
(when i1
(multiple-value-bind (i2 j2) (solve-bezout h k rest 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))))