結果

問題 No.1279 Array Battle
ユーザー sansaquasansaqua
提出日時 2020-11-23 12:20:19
言語 Common Lisp
(sbcl 2.3.8)
結果
AC  
実行時間 80 ms / 2,000 ms
コード長 6,433 bytes
コンパイル時間 528 ms
コンパイル使用メモリ 46,340 KB
実行使用メモリ 27,320 KB
最終ジャッジ日時 2023-09-30 23:43:58
合計ジャッジ時間 2,048 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
23,344 KB
testcase_01 AC 8 ms
23,276 KB
testcase_02 AC 9 ms
25,320 KB
testcase_03 AC 9 ms
23,192 KB
testcase_04 AC 9 ms
23,228 KB
testcase_05 AC 9 ms
23,260 KB
testcase_06 AC 10 ms
25,384 KB
testcase_07 AC 8 ms
23,276 KB
testcase_08 AC 10 ms
27,320 KB
testcase_09 AC 9 ms
25,268 KB
testcase_10 AC 9 ms
25,320 KB
testcase_11 AC 9 ms
25,300 KB
testcase_12 AC 10 ms
23,356 KB
testcase_13 AC 17 ms
25,448 KB
testcase_14 AC 16 ms
23,380 KB
testcase_15 AC 78 ms
25,852 KB
testcase_16 AC 80 ms
25,460 KB
testcase_17 AC 76 ms
23,300 KB
testcase_18 AC 79 ms
23,480 KB
testcase_19 AC 77 ms
23,348 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 30 SEP 2023 11:43:55 PM):
; processing (IN-PACKAGE :CL-USER)
; processing (DEFPARAMETER *OPT* ...)
; processing (SET-DISPATCH-MACRO-CHARACTER #\# ...)
; processing (DEFINE-INT-TYPES 2 ...)
; processing (DEFCONSTANT +MOD+ ...)
; processing (DEFMACRO DBG ...)
; processing (DECLAIM (INLINE PRINTLN))
; processing (DEFUN PRINTLN ...)
; processing (DEFPACKAGE :CP/MAP-PERMUTATIONS ...)
; processing (IN-PACKAGE :CP/MAP-PERMUTATIONS)
; processing (DECLAIM (INLINE MAP-PERMUTATIONS!))
; processing (DEFUN MAP-PERMUTATIONS! ...)
; processing (DECLAIM (INLINE MAP-COMBINATIONS))
; processing (DEFUN MAP-COMBINATIONS ...)
; processing (DECLAIM (INLINE MAP-PERMUTATIONS))
; processing (DEFUN MAP-PERMUTATIONS ...)
; processing (DEFMACRO DO-PERMUTATIONS! ...)
; processing (DEFMACRO DO-COMBINATIONS ...)
; processing (DEFMACRO DO-PERMUTATIONS ...)
; processing (USE-PACKAGE :CP/MAP-PERMUTATIONS ...)
; processing (IN-PACKAGE :CL-USER)
; processing (DEFUN MAIN ...)
; processing (MAIN)

; wrote /home/judge/data/code/Main.fasl
; compilation finished in 0:00:00.097

ソースコード

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)))))
#+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)
  #+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)))

(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
;;;
;;; Permutation and Combination
;;;

(defpackage :cp/map-permutations
  (:use :cl)
  (:export #:map-permutations! #:map-combinations #:map-permutations
           #:do-permutations! #:do-combinations #:do-permutations))
(in-package :cp/map-permutations)

(declaim (inline map-permutations!))
(defun map-permutations! (function vector &optional (start 0) end)
  "Destructively permutes VECTOR[START] ... VECTOR[END-1] and applies FUNCTION
to VECTOR each time. VECTOR comes back to the original order in the end."
  (declare (vector vector)
           ((mod #.array-total-size-limit) start)
           ((or null (mod #.array-total-size-limit)) end))
  (let ((end (or end (length vector))))
    (labels ((recur (start)
               (declare ((mod #.array-total-size-limit) start))
               (if (> start end)
                   (funcall function vector)
                   (loop initially (recur (+ 1 start))
                         for i from (+ 1 start) below end
                         do (rotatef (aref vector start) (aref vector i))
                            (recur (+ 1 start))
                            (rotatef (aref vector start) (aref vector i))))))
      (recur start))))

;; NOTE: It tends to be slow on SBCL version earlier than 1.5.0, as
;; constant-folding of ARRAY-ELEMENT-TYPE doesn't work.
(declaim (inline map-combinations))
(defun map-combinations (function vector length)
  "Applies FUNCTION to each combination of given length of VECTOR. Note that the
vector passed to FUNCTION is allocated only once and will be recycled. The
consequence is undefined when any of these two vectors are modified in FUNCION."
  (declare (vector vector)
           ((mod #.array-total-size-limit) length))
  (assert (<= length (length vector)))
  (let* ((n (length vector))
         (result (make-array length :element-type (array-element-type vector))))
    (labels ((recur (pos prev)
               (if (= pos length)
                   (funcall function result)
                   (loop for i from (+ 1 prev) below n
                         do (setf (aref result pos) (aref vector i))
                            (recur (+ 1 pos) i)))))
      (recur 0 -1))))

(declaim (inline map-permutations))
(defun map-permutations (function vector &optional k)
  "Applies FUNCTION to each permutation of length K of VECTOR. Note that the
vector passed to FUNCTION will be recycled."
  (declare (vector vector))
  (map-combinations (lambda (c) (map-permutations! function c))
                    vector
                    (or k (length vector))))

(defmacro do-permutations! ((var vector &optional (start 0) end) &body body)
  `(block nil (map-permutations! (lambda (,var) ,@body) ,vector ,start ,end)))

(defmacro do-combinations ((var vector length) &body body)
  `(block nil (map-combinations (lambda (,var) ,@body) ,vector ,length)))

(defmacro do-permutations ((var vector &optional k) &body body)
  `(block nil (map-permutations (lambda (,var) ,@body) ,vector ,k)))

;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/map-permutations :cl-user))
(in-package :cl-user)

;;;
;;; Body
;;;

(defun main ()
  (let* ((n (read))
         (as (make-array n :element-type 'uint31 :initial-element 0))
         (bs (make-array n :element-type 'uint31 :initial-element 0))
         (max-score -1)
         (res 0))
    (dotimes (i n)
      (setf (aref as i) (read)))
    (dotimes (i n)
      (setf (aref bs i) (read)))
    (do-permutations! (perm as)
      (let ((score (loop for a across perm
                         for b across bs
                         sum (max 0 (- a b)))))
        (cond ((> score max-score)
               (setq max-score score
                     res 1))
              ((= score max-score)
               (incf res)))))
    (println res)))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+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/1279"))

#+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 (or (> sb-c::*compiler-warning-count* 0)
            sb-c::*undefined-warnings*)
    (error "count: ~D, undefined warnings: ~A"
           sb-c::*compiler-warning-count*
           sb-c::*undefined-warnings*)))

;; To run: (5am:run! :sample)
#+swank
(5am:test :sample
  (5am:is
   (equal "1
"
          (run "2
3 4
1 4
" nil)))
  (5am:is
   (equal "6
"
          (run "3
5 5 5
7 5 6
" nil)))
  (5am:is
   (equal "28
"
          (run "5
6 5 5 4 4
1 3 5 7 9
" nil))))
0