結果

問題 No.1894 Delete AB
ユーザー motoshiramotoshira
提出日時 2022-04-08 22:50:37
言語 Common Lisp
(sbcl 2.3.8)
結果
AC  
実行時間 37 ms / 2,000 ms
コード長 7,555 bytes
コンパイル時間 349 ms
コンパイル使用メモリ 39,424 KB
実行使用メモリ 28,544 KB
最終ジャッジ日時 2024-05-06 08:30:01
合計ジャッジ時間 1,686 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
22,400 KB
testcase_01 AC 21 ms
27,648 KB
testcase_02 AC 21 ms
27,648 KB
testcase_03 AC 33 ms
26,624 KB
testcase_04 AC 35 ms
27,264 KB
testcase_05 AC 36 ms
27,648 KB
testcase_06 AC 35 ms
27,648 KB
testcase_07 AC 35 ms
27,904 KB
testcase_08 AC 37 ms
28,544 KB
testcase_09 AC 19 ms
25,600 KB
testcase_10 AC 21 ms
26,368 KB
testcase_11 AC 19 ms
26,752 KB
testcase_12 AC 20 ms
26,624 KB
testcase_13 AC 20 ms
27,520 KB
testcase_14 AC 19 ms
27,520 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 06 MAY 2024 08:29:57 AM):

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

ソースコード

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 (load "~/ghq/github.com/motoshira/atcoder-submission/ac-tools/act.lisp")
  #-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 expression
   #'(lambda (stream c2 n)
       (declare (ignore c2 n))
       (labels ((recursive-find (item tree)
                  (when tree
                    (cond
                      ((consp (first tree))
                       (or (recursive-find item (first tree))
                           (recursive-find item (rest tree))))
                      (t
                       (or (eq (first tree) item)
                           (recursive-find item (rest tree))))))))
         (let* ((form (read stream t nil t))
                (lambda-list (cond
                               ((recursive-find '%3 form)
                                '(%1 %2 %3))
                               ((recursive-find '%2 form)
                                '(%1 %2))
                               ((recursive-find '% form)
                                '(%))
                               (t
                                '()))))
           `(lambda ,lambda-list ,form)))))

  (set-dispatch-macro-character
   #\# #\>
   ;; debug print
   #'(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)
  (let ((cnt (gensym)))
    `(loop :for ,cnt :of-type fixnum :below ,count
           :with ,var :of-type fixnum := ,start
           :do (progn ,@body)
           :do (incf ,var (the fixnum ,step)))))

(defmacro condp (form test &body cases)
  `(cond
     ,@(mapcar (lambda (case)
                 (let* ((key (first case))
                        (test (if (atom key)
                                  `(funcall ,test ,form ,key)
                                  `(find ,form ',key :test ,test))))
                   `(,test
                     (progn
                       ,@(rest case)))))
               cases)
     (t (error "No matching case found for ~a" ,form))))

(defmacro nlet-tail (name binds &body body)
  (let* ((args (mapcar #'first binds))
         (init-values (mapcar #'second binds))
         (types (mapcar #'third binds))
         (outer (gensym "OUTER"))
         (loop (gensym "LOOP"))
         (vals (loop :for i :below (length args) :collect (gensym i)))
         (types-and-args (mapcar #'list types args))
         (args-and-inits (mapcar #'list args init-values)))
    `(macrolet ((,name (,@vals)
                  `(progn
                     (psetf ,@(apply #'nconc
                                     (mapcar (lambda (arg val &optional type)
                                               (if type
                                                   `((the ,type ,arg) (the ,type ,val))
                                                   `(,arg ,val)))
                                             ',args
                                             (list ,@vals)
                                             ',types)))
                     (go ,',loop))))
       (let (,@args-and-inits)
         ,(when (first types)
            `(declare ,@types-and-args))
         (block ,outer
           (tagbody ,loop
              (return-from ,outer
                (progn
                  ,@body))))))))

(defmacro aif (test then &optional else)
  `(let ((it ,test))
     (if it
         ,then
         ,else)))

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

(defmacro aprog1 (result &body forms)
  `(let ((it ,result))
     ,@forms
     it))

(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*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 obj
      (princ obj stream)
      (terpri stream))))

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

(declaim (inline read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  ;; Ref: https://competitive12.blogspot.com/2020/03/common-lisp.html
  ;;        partially modified
  (declare (inline read-byte))
  (let ((minus nil)
        (res 0))
    (declare (boolean minus)
             (fixnum res))
    (labels ((%read-byte ()
               (the fixnum #+swank (char-code (read-char in nil #\Nul))
                           #-swank (read-byte in nil #.(char-code #\Nul))))
             (%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 := (%read-byte)
                     :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 := (%read-byte)
                     :do (cond
                           ((%digit-p byte)
                            (setf (the fixnum res) (the fixnum (+ (the fixnum (* res 10)) (%byte->num byte)))))
                           (t (return))))))
      (declare (inline %read-byte %byte->num %digit-p %first-proc! %rest-proc!))
      (%first-proc!)
      (%rest-proc!)
      (the fixnum (if minus (- res) res)))))

;;;
;;; Body
;;;

(in-package #:cl-user)

(defun solve (m s)
  (let ((res nil))
    (do-iota (i m)
      (while (and (rest res)
                  (char= (char s i) #\B)
                  (char= (first res) #\B)
                  (char= (second res) #\A))
        (pop res)
        (pop res))
      (push (char s i) res))
    (coerce (reverse res) 'string)))

(defun main ()
  (let ((n (read)))
    (do-iota (_ n)
      (let ((m (read-fixnum))
            (s (read-line)))
        (println (solve m s))))))

#-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