結果

問題 No.1358 [Zelkova 2nd Tune *] 語るなら枚数を...
ユーザー sansaquasansaqua
提出日時 2021-01-22 22:49:04
言語 Common Lisp
(sbcl 2.5.0)
結果
AC  
実行時間 1,625 ms / 2,000 ms
コード長 10,510 bytes
コンパイル時間 555 ms
コンパイル使用メモリ 58,884 KB
実行使用メモリ 23,296 KB
最終ジャッジ日時 2024-12-28 04:40:14
合計ジャッジ時間 9,862 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 28 DEC 2024 04:40:04 AM):

; file: /home/judge/data/code/Main.lisp
; in: DEFUN SOLVE-BEZOUT
;     (* 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
;                         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::X0 MAX)
; 
; note: forced to do GENERIC-- (cost 10)
;       unable to do inline fixnum arithmetic (cost 2) because:
;       The first argument is a (INTEGER -21267647932558653961849226946058125312
;                                21267647932558653957237540927630737409), not a FIXNUM.
;       The second argument is a (OR NULL (UNSIGNED-BYTE 31)), not a FIXNUM.
;   

ソースコード

diff #
プレゼンテーションモードにする

(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))))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0