Submission #6035280

---

Source Code Expand

;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam))
  #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
;; unfinished.

(defun find-optimum (sequence predicate &key (start 0) end)
  "Returns an index x that satisfies (NOT (FUNCALL PREDICATE SEQUENCE[y]
SEQUENCE[x])) (i.e. SEQUENCE[x] >= SEQUENCE[y]) for all the indices y and
returns SEQUENCE[x] as the second value."
  (declare ((or null (integer 0 #.most-positive-fixnum)) end)
           ((integer 0 #.most-positive-fixnum) start)
           (function predicate)
           (sequence sequence))
  (etypecase sequence
    (list (error "Not implemented yet."))
    (vector
     (let ((end (or end (length sequence))))
       (unless (<= start end)
         (error "Can't find optimal value in null interval [~A, ~A)" start end))
       (let ((optimum (aref sequence 0))
             (index 0))
         (dotimes (i (length sequence) (values index optimum))
           (unless (funcall predicate optimum (aref sequence i))
             (setq optimum (aref sequence i)
                   index i))))))))

(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)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body


;; 前処理:
;; すべての数がN以上になるまでシミュレーションする。
;; 主処理:
;; N+1回の操作後には、最大の数がN+1減ってほかの数が変化しないので
;; すべての数が2N以下になる操作回数が数えられる。
;; 後処理:
;; すべての数がN未満になるまでシミュレーションする。

(defun main ()
  (let* ((n (read))
         (as (make-array n :element-type 'fixnum))
         (res 0))
    (dotimes (i n) (setf (aref as i) (read)))
    ;; prelude
    (loop
      (when (or (every (lambda (a) (< a n)) as)
                (every (lambda (a) (>= a n)) as))
        (return))
      (let ((pos (find-optimum as #'>)))
        (incf res)
        (decf (aref as pos) n)
        (dotimes (i n)
          (unless (= i pos)
            (incf (aref as i))))))
    ;; main
    (dotimes (i n)
      (when (> (aref as i) (* 2 n))
        (let* ((delta (* (+ n 1) (ceiling (- (aref as i) (* 2 n)) (+ n 1))))
               (count (* (+ n 1) (floor delta (+ n 1)))))
          (incf res count)
          (decf (aref as i) delta))))
    ;; postlude
    (loop
      (when (every (lambda (a) (< a n)) as)
        (return))
      (let ((pos (find-optimum as #'>)))
        (incf res)
        (decf (aref as pos) n)
        (dotimes (i n)
          (unless (= i pos)
            (incf (aref as i))))))
    (println res)))

#-swank(main)

Submission Info

Judge Result