(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 ;;; from UIOP ;;; Copyright (c) 2001-2019 Daniel Barlow and contributors ;;; ;;; Permission is hereby granted, free of charge, to any person obtaining ;;; a copy of this software and associated documentation files (the ;;; "Software"), to deal in the Software without restriction, including ;;; without limitation the rights to use, copy, modify, merge, publish, ;;; distribute, sublicense, and/or sell copies of the Software, and to ;;; permit persons to whom the Software is furnished to do so, subject to ;;; the following conditions: ;;; ;;; The above copyright notice and this permission notice shall be ;;; included in all copies or substantial portions of the Software. ;;; ;;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, ;;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF ;;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND ;;; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE ;;; LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION ;;; OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION ;;; WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. (defpackage :cp/split-string (:use :cl) (:export #:split-string)) (in-package :cp/split-string) (declaim (inline split-string)) (defun split-string (string &key max (separator '(#\Space #\Tab))) (declare (string string)) (block () (let ((list nil) (words 0) (end (length string))) (declare ((integer 0 #.most-positive-fixnum) words end)) (when (zerop end) (return nil)) (flet ((separatorp (char) (find char separator)) (done () (return (cons (subseq string 0 end) list)))) (loop :for start = (if (and max (>= words (1- max))) (done) (position-if #'separatorp string :end end :from-end t)) :do (when (null start) (done)) (push (subseq string (1+ start) end) list) (incf words) (setf end start)))))) (defpackage :cp/dictionary-order (:use :cl) (:export #:dict< #:dict<=)) (in-package :cp/dictionary-order) ;; based on UIOP:LEXICOGRAPHIC< (declaim (inline dict<)) (defun dict< (element< x y) "Lexicographically compare two sequences using the function element< to compare elements. element< is a strict total order; the resulting order on X and Y will also be strict." (etypecase x (list (check-type y list) (labels ((recur (x y) (cond ((null y) nil) ((null x) t) ((funcall element< (car x) (car y)) t) ((funcall element< (car y) (car x)) nil) (t (recur (cdr x) (cdr y)))))) (recur x y))) (vector (check-type y vector) (let ((xlen (length x)) (ylen (length y))) (labels ((recur (i j) (declare ((integer 0 #.most-positive-fixnum) i j)) (cond ((= j ylen) nil) ((= i xlen) t) ((funcall element< (aref x i) (aref y i)) t) ((funcall element< (aref y i) (aref x i)) nil) (t (recur (+ i 1) (+ j 1)))))) (recur 0 0)))))) (declaim (inline dict<=)) (defun dict<= (element< x y) (or (dict< element< x y) (not (dict< element< y x)))) ;; BEGIN_USE_PACKAGE (eval-when (:compile-toplevel :load-toplevel :execute) (use-package :cp/dictionary-order :cl-user)) (eval-when (:compile-toplevel :load-toplevel :execute) (use-package :cp/split-string :cl-user)) (in-package :cl-user) ;;; ;;; Body ;;; (defun main () (let ((abc0 (mapcar #'read-from-string (split-string (read-line) :separator '(#\.)))) (abc1 (mapcar #'read-from-string (split-string (read-line) :separator '(#\.))))) (write-line (if (dict<= #'< abc1 abc0) "YES" "NO")))) #-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/138")) #+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 "YES " (run "4.8.1 4.8.0 " nil))) (5am:is (equal "NO " (run "0.0.0 1.1.1 " nil))) (5am:is (equal "NO " (run "1.2.3 3.2.1 " nil))))