結果

問題 No.1336 Union on Blackboard
ユーザー EnderedEndered
提出日時 2021-02-15 20:03:54
言語 Common Lisp
(sbcl 2.3.8)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 7,964 bytes
コンパイル時間 561 ms
コンパイル使用メモリ 53,576 KB
実行使用メモリ 30,400 KB
最終ジャッジ日時 2023-09-30 18:22:04
合計ジャッジ時間 3,551 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
外部呼び出し有り
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 20 ms
26,668 KB
testcase_01 AC 23 ms
24,712 KB
testcase_02 AC 23 ms
27,004 KB
testcase_03 AC 24 ms
25,096 KB
testcase_04 AC 22 ms
28,332 KB
testcase_05 AC 24 ms
27,216 KB
testcase_06 AC 22 ms
26,172 KB
testcase_07 AC 23 ms
30,280 KB
testcase_08 AC 22 ms
24,696 KB
testcase_09 AC 26 ms
30,396 KB
testcase_10 AC 25 ms
24,664 KB
testcase_11 AC 27 ms
28,208 KB
testcase_12 AC 25 ms
24,652 KB
testcase_13 AC 25 ms
24,656 KB
testcase_14 AC 27 ms
28,280 KB
testcase_15 AC 26 ms
27,008 KB
testcase_16 AC 27 ms
30,400 KB
testcase_17 AC 27 ms
28,352 KB
testcase_18 AC 26 ms
27,112 KB
testcase_19 AC 26 ms
26,936 KB
testcase_20 AC 24 ms
24,664 KB
testcase_21 AC 27 ms
27,136 KB
testcase_22 AC 26 ms
25,124 KB
testcase_23 AC 26 ms
28,404 KB
testcase_24 AC 24 ms
24,680 KB
testcase_25 AC 24 ms
24,652 KB
testcase_26 AC 26 ms
26,824 KB
testcase_27 AC 26 ms
25,048 KB
testcase_28 AC 27 ms
28,444 KB
testcase_29 AC 26 ms
26,808 KB
testcase_30 AC 19 ms
26,536 KB
testcase_31 AC 18 ms
26,892 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 30 SEP 2023 06:22:00 PM):
; processing (UNLESS (MEMBER :CHILD-SBCL ...) ...)
; processing (DEFMACRO DPLINE ...)
; processing (DEFMACRO DPHASH ...)
; processing (DEFMACRO TEST ...)
; file: /home/judge/data/code/Main.lisp
; in: DEFMACRO TEST
;     (DEFMACRO TEST ((FUNC &BODY ARGS) &OPTIONAL (OUT-STREAM))
;       (LET ((EVALED-ARGS (GENSYM)))
;         `(LET ((,EVALED-ARGS #))
;            (FORMAT T "~w: ~w ~%" `(,',FUNC ,@,EVALED-ARGS)
;                    (APPLY #',FUNC ,EVALED-ARGS)))))
; --> SB-INT:NAMED-DS-BIND SB-INT:BINDING* 
; ==>
;   (LET* ((#:G0 (SB-C::CHECK-DS-LIST (CDR #:EXPR) 1 2 '(# # &OPTIONAL #)))
;          (#:G1 (SB-C::CHECK-DS-LIST/&REST (POP #:G0) 1 1 '(# FUNC &BODY ARGS)))
;          (FUNC (POP #:G1))
;          (ARGS #:G1)
;          (OUT-STREAM
;           (IF #:G0
;               (POP #:G0))))
;     (DECLARE (SB-C::CONSTANT-VALUE FUNC ARGS OUT-STREAM))
;     (BLOCK TEST
;       (LET ((EVALED-ARGS #))
;         `(LET (#)
;            (FORMAT T "~w: ~w ~%" `# #)))))
; 
; caught STYLE-WARNING:
;   The variable OUT-STREAM is defined but never used.

; file: /home/judge/data/code/Main.lisp
; in: DEFMACRO TEST
;     (DEFMACRO TEST ((FUNC &BODY ARGS) &OPTIONAL (OUT-STREAM))
;       (LET ((EVALED-ARGS (GENSYM)))
;         `(LET ((,EVALED-ARGS #))
;            (FORMAT T "~w: ~w ~%" `(,',FUNC ,@,EVALED-ARGS)
;                    (APPLY #',FUNC ,EVALED-ARGS)))))
; --> PROGN EVAL-WHEN SB-C::%DEFMACRO SB-C::%DEFMACRO SB-INT:NAMED-LAMBDA 
; --> FUNCTION SB-INT:NAMED-DS-BIND SB-INT:BINDING* 
; ==>
;   (LET* ((#:G0 (SB-C::CHECK-DS-LIST (CDR #:EXPR) 1 2 '(# # &OPTIONAL #)))
;          (#:G1 (SB-C::CHECK-DS-LIST/&REST (POP #:G0) 1 1 '(# FUNC &BODY ARGS)))
;          (FUNC (POP #:G1))
;          (ARGS #:G1)
;          (OUT-STREAM
;           (IF #:G0
;               (POP #:G0))))
;     (DECLARE (SB-C::CONSTANT-VALUE FUNC ARGS OUT-STREAM))
;     (BLOCK TEST
;       (LET ((EVALED-ARGS #))
;         `(LET (#

ソースコード

diff # 

#-swank
(unless (member :child-sbcl *features*)
  "I refered from https://competitive12.blogspot.com/2020/03/common-lisp.html thank you!"
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "256MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))
(defmacro dpline (name args memo-size &body body)
  (let ((memo (gensym)))
    `(let ((,memo (make-array ,memo-size :initial-element nil)))
       (defun ,name ,args
         (or (aref ,memo ,@args)
             (setf (aref ,memo ,@args)
                   ,@body))))))

(defmacro dphash (name args &body expr)
  `(let ((table (make-hash-table :test #'equal)))
     (defun  ,name ,args 
       (or (gethash (list ,@args) table)
           (setf (gethash (list ,@args) table)
                 (progn 
                   ,@expr))))))

(defmacro test ((func &body args) &optional (out-stream))
  (let ((evaled-args (gensym)))
    `(let ((,evaled-args (list ,@args)))
       (format t "~w: ~w ~%" `(,',func ,@,evaled-args) (apply #',func ,evaled-args)))))

(defmacro dplabels (funcs &body body)
  (let ((tables (loop for func in funcs collect (gensym))))
    `(let ,(mapcar (lambda (table) `(,table (make-hash-table :test #'equal)))
            tables)
       (labels ,(mapcar (lambda (func table)
                          (let ((name (first func))
                                (args (second func))
                                (body (cddr func))
                                (ok (gensym))
                                (val (gensym)))
                            `(,name ,args
                                    (multiple-value-bind (,val ,ok)
                                      (gethash (list ,@args) ,table)
                                      (if ,ok ,val
                                          (setf (gethash (list ,@args) ,table)
                                                (progn ,@body)))))))
                        funcs tables)
         ,@body))))

(defmacro dpfun (name args &body body)
  (let ((f (gensym)))
    `(dplabels ((,f ,args ,@body))
       (defun ,name (&rest args)
         (apply #',f args)))))


(defun split (x str)
  (let ((pos (search x str))
        (size (length x)))
    (if pos
        (cons (subseq str 0 pos)
              (split x (subseq str (+ pos size))))
        (list str))))

(defmacro collect-times (time body)
  `(loop repeat ,time collect ,body))

(defun read-times (time)
  (collect-times time (read)))

(defmacro aif (expr then else)
  `(let ((it ,expr))
     (if it ,then ,else)))

(defmacro awhen (expr &rest then)
  `(aif ,expr (progn ,@then) nil))

(defun comulative (function list &key base)
  (if base
      (comulative function (cons base list))
      (do ((lst (cdr list) (cdr lst))
           (acc (list (car list))))
          ((null lst) (reverse acc))
        (push (funcall function (car acc) (car lst)) acc))))

(defun binary-search (function left right
                      &optional
                        (eps 1)
                        (average-function (lambda (x y) (ash (+ x y) -1))))
  (if (<= (abs (- left right)) eps)
      right
      (let ((mid (funcall average-function left right)))
        (if (funcall function mid)
            (binary-search function left mid eps average-function)
            (binary-search function mid right eps average-function)))))

(defun arithmetic-mean (&rest body)
  (/ (apply #'+ body) (length body)))

(defvar +MOD+ (+ (expt 10 9) 7))

(defun range-0-n (n &optional (step 1))
  (loop for i from 0 below n by step collect i))

(defun range-1-n (n &optional (step 1))
  (loop for i from 1 below n by step collect i))

(defun range-a-b (a b &optional (step 1))
  (loop for i from a below b by step collect i))

(defun map-0-n (function n &optional (step 1))
  (mapcar function (range-0-n n step)))

(defun map-1-n (function n &optional (step 1))
  (mapcar function (range-1-n n step)))

(defun map-a-b (function a b &optional (step 1))
  (mapcar function (range-a-b a b step)))

(defun read-string (&optional (stream *standard-input*))
  (labels ((is-empty (x)
             (or (char= x #\space) (char= x #\newline))))
    (loop for char = (read-char stream)
          with result
          when (and result (is-empty char))
            do (return (concatenate 'string (nreverse result)))
          when (null (is-empty char))
            do (push char result))))

(defun merge-sort (lst &optional (compare #'<))
  (let ((turn 0))
    (labels ((merge-list (a b a-length b-length)
               (cond ((zerop a-length) b)
                     ((zerop b-length) a)
                     ((funcall compare (car b) (car a))
                      (incf turn a-length)
                      (cons (car b)
                            (merge-list a (cdr b) a-length (1- b-length))))
                     (t
                      (cons (car a)
                            (merge-list (cdr a) b (1- a-length) b-length)))))
             (f (lst length)
               (if (= length 1)
                   lst
                   (let ((mid (ash length -1)))
                     (merge-list (f (subseq lst 0 mid) mid)
                                 (f (subseq lst mid) (- length mid))
                                 mid
                                 (- length mid))))))
      (values (f lst (length lst)) turn))))

(defun group (lst &optional (test #'eql) (key nil))
  (let ((table (make-hash-table :test test)))
    (mapc (lambda (x)
            (push x (gethash (if key (funcall key x) x) table)))
          lst)
    (loop for value being each hash-value in table
          collect value)))

(defun nearby (&rest args)
  (let ((current (subseq args 0 (ash (length args) -1)))
        (validator (subseq args (ash (length args) -1)))
        (res nil))
    (labels ((check ()
               (every (lambda (x y) (and (<= 0 x) (< x y)))
                      current validator))
             (f (lst)
               (unless lst (return-from f))
               (let ((x (car lst)))
                 (setf (car lst) (1+ x))
                 (when (check) (push (copy-list current) res))
                 (setf (car lst) (1- x))
                 (when (check) (push (copy-list current) res))
                 (setf (car lst) x))
               (f (cdr lst))))
      (f current)
      res)))

(defun make-primes (max-number)
  (let ((array (make-array (1+ max-number) :initial-element t)))
    (loop for i from 2 to max-number
          for is-prime = (aref array i)
          when is-prime collect i
          when is-prime
          do (loop for j from (* 2 i) to max-number by i
                   do (setf (aref array j) nil)))))

(defun make-is-prime (max-number)
  (let ((primes (make-primes max-number))
        (table (make-array (1+ max-number) :initial-element nil)))
    (dolist (i primes)
      (setf (aref table i) t))
    (defun is-prime (x)
      (aref table x))))


(defparameter +MOD+ (+ 7 (expt 10 9)))
(defmacro mod+ (&body args)
  (reduce (lambda (a b) `(mod (+ ,a ,b) +MOD+))
          args))
(defmacro mod- (&body args)
  (reduce (lambda (a b) `(mod (- ,a ,b) +MOD+))
          args))
(defmacro mod* (&body args)
  (reduce (lambda (a b) `(mod (* ,a ,b) +MOD+))
          args))
(defun modpow (base power)
  (if (zerop power)
      1
      (let ((base2 (mod* base base)))
        (mod* (if (oddp power) base 1)
              (modpow base2 (ash power -1))))))
(defun modinv (x)
  (modpow x (- +MOD+ 2)))
(defmacro mod/ (x &body args)
  `(mod* ,x 
         (modinv (mod* ,@args))))

(defun main (n a)
  (reduce (lambda (a b)
	    (mod+ a b (mod* a b)))
	  a))

#-swank
(let ((time (read)))
  (dotimes (_ time)
    (let* ((n (read))
	   (a (read-times n)))
      (format t "~a~%" (main n a)))))
0