結果

問題 No.3072 Sum of sqrt(x)
ユーザー motoshiramotoshira
提出日時 2022-09-06 23:03:48
言語 Common Lisp
(sbcl 2.3.8)
結果
WA  
実行時間 -
コード長 6,769 bytes
コンパイル時間 906 ms
コンパイル使用メモリ 36,352 KB
実行使用メモリ 340,096 KB
最終ジャッジ日時 2024-11-21 23:08:04
合計ジャッジ時間 61,527 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
28,160 KB
testcase_01 WA -
testcase_02 AC 9 ms
28,288 KB
testcase_03 AC 9 ms
261,120 KB
testcase_04 AC 10 ms
28,160 KB
testcase_05 AC 8 ms
22,912 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 638 ms
80,128 KB
testcase_09 AC 1,007 ms
80,128 KB
testcase_10 OLE -
testcase_11 OLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 OLE -
testcase_15 OLE -
testcase_16 OLE -
testcase_17 OLE -
testcase_18 OLE -
testcase_19 OLE -
testcase_20 OLE -
testcase_21 OLE -
testcase_22 OLE -
testcase_23 OLE -
testcase_24 OLE -
testcase_25 OLE -
testcase_26 OLE -
testcase_27 OLE -
testcase_28 WA -
testcase_29 OLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 21 NOV 2024 11:07:06 PM):

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

ソースコード

diff # 

(in-package #:cl-user)

;;;
;;; Init
;;;

(eval-when (:compile-toplevel :load-toplevel :execute)
  #+swank (declaim (optimize (speed 3) (safety 2)))
  #-swank (declaim (optimize (speed 3) (safety 0) (debug 0)))
  #-swank (declaim (sb-ext:muffle-conditions sb-ext:compiler-note))
  #-swank (sb-ext:disable-debugger))

;;;
;;; Reader Macros
;;;

(eval-when (:compile-toplevel :load-toplevel :execute)
  (set-dispatch-macro-character
   #\# #\f
   #'(lambda (stream c2 n)
       (declare (ignore c2 n))
       (let ((form (read stream t nil t)))
         `(lambda (&optional %) (declare (ignorable %)) ,form))))

  (set-dispatch-macro-character
   #\# #\>
   #'(lambda (stream c2 n)
       (declare (ignore c2 n))
       (let ((form (read stream t nil t)))
         (declare (ignorable form))
         #-swank nil
         #+swank (if (atom form)
                     `(format *error-output* "~a => ~a~&" ',form ,form)
                     `(format *error-output* "~a => ~a~&" ',form `(,,@form)))))))

;;;
;;; Libraries
;;;

;;;
;;; Macros
;;;

(in-package #:cl-user)

(defmacro do-iota ((var count &optional (start 0) (step 1)) &body body)
  (check-type step integer)
  (let* ((last (gensym))
         (terminate (if (plusp step) `(>= ,var ,last) `(<= ,var ,last))))
    `(let ((,last (+ ,start (the fixnum (* ,step ,count)))))
       (declare (fixnum ,last))
       (do
        ((,var ,start (+ ,var ,step)))
        (,terminate)
         (progn ,@body)))))

(defmacro awhen (test &body forms)
  `(let ((it ,test))
     (when it
       ,@forms)))

(defmacro while (test &body body)
  `(loop while ,test do (progn ,@body)))

;;;
;;; I/O
;;;

(in-package #:cl-user)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  #+sbcl (declare (sb-kernel:ansi-stream stream))
  (let ((*read-default-float-format* 'double-float))
    (prog1 obj
      (princ obj stream)
      (terpri stream))))

(declaim (inline %read-byte))
(defun %read-byte (&optional (stream *standard-input*))
  (declare (inline read-byte)
           #+(and sbcl (not swank)) (sb-kernel:ansi-stream stream))
  (the fixnum #+swank (char-code (read-char stream nil #\Nul))
              #-swank (read-byte stream nil #.(char-code #\Nul))))

(declaim (inline read-fixnum))
(defun read-fixnum (&optional (in *standard-input*) (byte-reader #'%read-byte))
  ;; Ref: https://competitive12.blogspot.com/2020/03/common-lisp.html
  ;;        partially modified
  (declare ((function (stream) (unsigned-byte 8)) byte-reader)
           (optimize (speed 3) (safety 0) (debug 0)))
  (let ((minus nil)
        (res 0))
    (declare (boolean minus)
             (fixnum res))
    (labels ((%byte->num (b)
               (the fixnum (- (the fixnum b) #.(char-code #\0))))
             (%digit-p (byte)
               (<= #.(char-code #\0) (the fixnum byte) #.(char-code #\9)))
             (%first-proc! ()
               (loop for byte of-type fixnum = (funcall byte-reader in)
                     do (cond
                          ((%digit-p byte)
                           (setf (the fixnum res) (%byte->num byte))
                           (return))
                          ((= byte #.(char-code #\Nul))
                           (error "EOF"))
                          ((= byte #.(char-code #\-))
                           (setf minus t)))))
             (%rest-proc! ()
               (loop for byte of-type fixnum = (funcall byte-reader in)
                     do (cond
                          ((%digit-p byte)
                           (setf (the fixnum res) (the fixnum (+ (the fixnum (* res 10)) (%byte->num byte)))))
                          (t (return))))))
      (declare (inline %byte->num %digit-p %first-proc! %rest-proc!))
      (%first-proc!)
      (%rest-proc!)
      (the fixnum (if minus (- res) res)))))

(declaim (inline read-base-char))
(defun read-base-char (&optional (stream *standard-input*))
  (code-char (%read-byte stream)))

(defun read-line-fast (&optional (stream *standard-input*))
  #+(and (not swank) sbcl) (declare (sb-kernel:ansi-stream stream))
  (loop with buffer of-type base-string = (make-array 0 :element-type 'base-char :fill-pointer 0)
        for c of-type base-char = (read-base-char stream)
        until (or (eql c #\Newline)
                  (eql c #\Nul))
        do (vector-push-extend c buffer)
        finally (return buffer)))

(declaim (inline parse-fixnum))
(defun parse-fixnum (string)
  (with-input-from-string (in string)
    (read-fixnum in #f(the (unsigned-byte 8)
                           (char-code (read-char % nil #\Nul nil))))))

(defun read-times (count &key (result-type 'list) (reader #'read-fixnum))
  (coerce (loop repeat count collect (funcall reader)) result-type))

(defmacro with-buffered-stdout (&body body)
  ;; Quoted from: https://competitive12.blogspot.com/2020/03/common-lisp.html
  (let ((out (gensym)))
    `(let ((,out (make-string-output-stream :element-type 'base-char)))
       (let ((*standard-output* ,out))
         ,@body)
       (write-string (get-output-stream-string ,out)))))

;;;
;;; Body
;;;

(in-package #:cl-user)

(defun sqrt-double (x)
  (declare (double-float x))
  (let ((lo 0d0)
        (hi #.(float (expt 10 10) 0d0)))
    (declare (double-float lo hi))
    (dotimes (_ 100)
      (let ((mid (/ (+ lo hi) 2)))
        (declare (double-float mid))
        (if (< (* mid mid)
               x)
            (setf lo mid)
            (setf hi mid))))
    lo))

(defun main ()
  (let* ((n (read))
         (cc (make-hash-table :test #'eql))
         (dd (make-hash-table :test #'eql))
         (sum 0d0))
    (declare (double-float sum))
    (with-buffered-stdout
      (dotimes (_ n)
        (let* ((x (read-fixnum))
               (r (sqrt-double (float x 0d0)))
               (d (- (* r r) (float x 0d0))))
          (incf (gethash x cc 0))
          (incf (gethash x dd 0d0) d)
          (let ((m (gethash x dd)))
            (when (> (abs m) 10e-19)
              (decf sum m)
              (setf (gethash x dd) 0d0
                    (gethash x cc) 0)))
          (incf sum r)
          (println sum))))))

#-swank (main)

;;;
;;; Debug
;;;

#+swank
(defun run ()
  (let ((*standard-input*
          (make-string-input-stream
           (with-output-to-string (*standard-output*)
             (run-program
              (truename "~/bin/copy-or-paste")
              '()
              :output *standard-output*)))))
    (main)))

;; Raise error on warning at compile time

#+(and sbcl (not swank))
(eval-when (:compile-toplevel)
  (when (or (plusp sb-c::*compiler-warning-count*)
            sb-c::*undefined-warnings*)
    (error "compiler-error-count:~a, undefined warnings:~a"
           sb-c::*compiler-warning-count*
           sb-c::*undefined-warnings*)))
0