結果

問題 No.1279 Array Battle
ユーザー sansaquasansaqua
提出日時 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

ソースコード

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