結果
| 問題 | No.897 compαctree |
| ユーザー |
 sansaqua
|
| 提出日時 | 2019-10-04 21:26:32 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
AC
|
| 実行時間 | 12 ms / 2,000 ms |
| コード長 | 7,702 bytes |
| コンパイル時間 | 1,141 ms |
| コンパイル使用メモリ | 45,908 KB |
| 実行使用メモリ | 30,648 KB |
| 最終ジャッジ日時 | 2024-04-14 10:11:26 |
| 合計ジャッジ時間 | 2,123 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 10 ms
26,664 KB |
| testcase_01 | AC | 11 ms
26,920 KB |
| testcase_02 | AC | 11 ms
26,788 KB |
| testcase_03 | AC | 11 ms
26,916 KB |
| testcase_04 | AC | 11 ms
26,668 KB |
| testcase_05 | AC | 11 ms
26,792 KB |
| testcase_06 | AC | 12 ms
30,648 KB |
| testcase_07 | AC | 11 ms
26,664 KB |
| testcase_08 | AC | 11 ms
26,408 KB |
| testcase_09 | AC | 11 ms
26,664 KB |
| testcase_10 | AC | 12 ms
30,628 KB |
| testcase_11 | AC | 10 ms
26,668 KB |
| testcase_12 | AC | 10 ms
26,664 KB |
| testcase_13 | AC | 11 ms
26,664 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 14 APR 2024 10:11:24 AM): ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.075
ソースコード
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
(sb-int:defconstant-eqx OPT
#+swank '(optimize (speed 3) (safety 2))
#-swank '(optimize (speed 3) (safety 0) (debug 0))
#'equal)
#+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
#-swank (set-dispatch-macro-character
#\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil nil t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy
;; BEGIN_INSERTED_CONTENTS
(declaim (inline bisect-left))
(defun bisect-left (target value &key (start 0) end (order #'<) (key #'identity))
"TARGET := vector | function (taking an integer argument)
ORDER := strict order
Analogue of lower_bound of C++ or bisect_left of Python: Returns the smallest
index (or input) i that fulfills TARGET[i] >= VALUE, where '>=' is the
complement of ORDER. In other words, this function returns the leftmost index at
which VALUE can be inserted with keeping the order. Therefore, TARGET must be
monotonically non-decreasing with respect to ORDER.
This function returns END if VALUE exceeds TARGET[END-1]. Note that the range
[START, END) is half-open. END must be explicitly specified if TARGET is
function. KEY is applied to each element of TARGET before comparison."
(declare (function key order)
(integer start)
((or null integer) end))
(macrolet
((body (accessor &optional declaration)
`(progn
(assert (<= start end))
(if (= start end) end
(labels
((%bisect-left (left ok)
;; TARGET[OK] >= VALUE always holds (assuming
;; TARGET[END] = +infinity)
,@(list declaration)
(let ((mid (ash (+ left ok) -1)))
(if (= mid left)
(if (funcall order (funcall key (,accessor target left)) value)
ok
left)
(if (funcall order (funcall key (,accessor target mid)) value)
(%bisect-left mid ok)
(%bisect-left left mid))))))
(%bisect-left start end))))))
(etypecase target
(vector
(let ((end (or end (length target))))
(body aref (declare ((integer 0 #.most-positive-fixnum) left ok)))))
(function
(assert end () "Requires END argument if TARGET is a function.")
(body funcall)))))
(declaim (inline bisect-right))
(defun bisect-right (target value &key (start 0) end (order #'<) (key #'identity))
"TARGET := vector | function (taking an integer argument)
ORDER := strict order
Analogue of upper_bound of C++ or bisect_right of Python: Returns the smallest
index (or input) i that fulfills TARGET[i] > VALUE. In other words, this
function returns the rightmost index at which VALUE can be inserted with keeping
the order. Therefore, TARGET must be monotonically non-decreasing with respect
to ORDER.
This function returns END if VALUE >= TARGET[END-1]. Note that the range [START,
END) is half-open. END must be explicitly specified if TARGET is function. KEY
is applied to each element of TARGET before comparison."
(declare (function key order)
(integer start)
((or null integer) end))
(macrolet
((body (accessor &optional declaration)
`(progn
(assert (<= start end))
(if (= start end)
end
(labels
((%bisect-right (left ok)
;; TARGET[OK] > VALUE always holds (assuming
;; TARGET[END] = +infinity)
,@(list declaration)
(let ((mid (ash (+ left ok) -1)))
(if (= mid left)
(if (funcall order value (funcall key (,accessor target left)))
left
ok)
(if (funcall order value (funcall key (,accessor target mid)))
(%bisect-right left mid)
(%bisect-right mid ok))))))
(%bisect-right start end))))))
(etypecase target
(vector
(when (null end)
(setf end (length target)))
(body aref (declare ((integer 0 #.most-positive-fixnum) left ok))))
(function
(assert end () "Requires END argument if TARGET is a function.")
(body funcall)))))
(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
;;;
(defun main ()
(let* ((q (read)))
(dotimes (_ q)
(let ((n (read))
(k (read)))
(println
(if (= k 1)
(- n 1)
(bisect-left (lambda (x)
(/ (- (expt k (+ x 1)) 1)
(- k 1)))
n
:end 1000)))))))
#-swank (main)
;;;
;;; Test and benchmark
;;;
#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
"Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
(labels ((ensure-last-lf (s)
(if (eql (uiop:last-char s) #\Linefeed)
s
(uiop:strcat s uiop:+lf+))))
(funcall test
(ensure-last-lf out-string)
(with-output-to-string (out)
(let ((*standard-output* out))
(with-input-from-string (*standard-input* (ensure-last-lf in-string))
(funcall function)))))))
#+swank
(defun get-clipbrd ()
(with-output-to-string (out)
(run-program "C:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))
#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))
#+swank
(defun run (&optional thing (out *standard-output*))
"THING := null | string | symbol | pathname
null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
(let ((*standard-output* out))
(etypecase thing
(null
(with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
(main)))
(string
(with-input-from-string (*standard-input* (delete #\Return thing))
(main)))
(symbol (5am:run! thing))
(pathname
(with-open-file (*standard-input* thing)
(main))))))
#+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)))