結果
| 問題 | No.1279 Array Battle |
| ユーザー |
 sansaqua
|
| 提出日時 | 2020-11-23 12:20:19 |
| 言語 | Common Lisp (sbcl 2.5.0) |
| 結果 |
AC
|
| 実行時間 | 64 ms / 2,000 ms |
| コード長 | 6,433 bytes |
| コンパイル時間 | 2,122 ms |
| コンパイル使用メモリ | 48,196 KB |
| 実行使用メモリ | 22,784 KB |
| 最終ジャッジ日時 | 2024-07-23 17:25:27 |
| 合計ジャッジ時間 | 1,266 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 23 JUL 2024 05:25:23 PM): ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.187
ソースコード
(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))))