Submission #4192722
Source Code Expand
(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 (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
;; BEGIN_INSERTED_CONTENTS
;; (with-memoizing (:hash-table :test #'equal :key #'cons)
;; (defun ...))
;; (with-memoizing (:array (10 10 * 10) :initial-element -1 :element-type 'fixnum)
;; (defun ...))
(defmacro with-memoizing (cache-attribs def-form)
(let* ((cache-attribs (if (atom cache-attribs) (list cache-attribs) cache-attribs))
(cache-type (first cache-attribs))
(dimensions-with-* (when (eql cache-type :array) (second cache-attribs)))
(dimensions (remove '* dimensions-with-*))
(rank (length dimensions))
(rest-attribs (ecase cache-type
(:hash-table (cdr cache-attribs))
(:array (cddr cache-attribs))))
(key (prog1 (getf rest-attribs :key) (remf rest-attribs :key)))
(cache-form (case cache-type
(:hash-table `(make-hash-table ,@rest-attribs))
(:array `(make-array ',dimensions ,@rest-attribs))))
(initial-element (when (eql cache-type :array)
(assert (member :initial-element rest-attribs))
(getf rest-attribs :initial-element))))
(let ((cache (gensym))
(value (gensym))
(present-p (gensym))
(name-alias (gensym))
(args-lst (gensym))
(indices (loop repeat rank collect (gensym))))
(labels ((make-cache-check-form (cache-type args)
(case cache-type
(:hash-table
`(let ((,args-lst (funcall ,(or key #'list) ,@args)))
(multiple-value-bind (,value ,present-p)
(gethash ,args-lst ,cache)
(if ,present-p
,value
(setf (gethash ,args-lst ,cache)
(,name-alias ,@args))))))
(:array
(let ((memoized-args (loop for dimension in dimensions-with-*
for arg in args
unless (eql dimension '*)
collect arg)))
(if key
`(multiple-value-bind ,indices
(funcall ,key ,@memoized-args)
(let ((,value (aref ,cache ,@indices)))
(if (eql ,initial-element ,value)
(setf (aref ,cache ,@indices)
(,name-alias ,@args))
,value)))
`(let ((,value (aref ,cache ,@memoized-args)))
(if (eql ,initial-element ,value)
(setf (aref ,cache ,@memoized-args)
(,name-alias ,@args))
,value)))))))
(make-reset-form (cache-type)
(case cache-type
(:hash-table `(setf ,cache (make-hash-table ,@rest-attribs)))
(:array `(prog1 nil
(fill (array-storage-vector ,cache) ,initial-element)))))
(make-reset-name (name)
(intern (format nil "RESET-~A" (symbol-name name))))
(extract-declarations (body)
(remove-if-not (lambda (form) (eql 'declare (car form))) body)))
(ecase (car def-form)
((defun)
(destructuring-bind (_ name args &body body) def-form
(declare (ignore _))
`(let ((,cache ,cache-form))
(defun ,(make-reset-name name) () ,(make-reset-form cache-type))
(defun ,name ,args
(labels ((,name-alias ,args ,@body))
(declare (inline ,name-alias))
,@(extract-declarations body)
,(make-cache-check-form cache-type args))))))
((nlet)
(destructuring-bind (_ name bindings &body body) def-form
(declare (ignore _))
`(let ((,cache ,cache-form))
(nlet ,name ,bindings
,(let ((args (mapcar (lambda (x) (if (atom x) x (car x))) bindings)))
`(labels ((,name-alias ,args ,@body))
(declare (inline ,name-alias))
,@(extract-declarations body)
,(make-cache-check-form cache-type args)))))))
((labels flet)
(destructuring-bind (_ definitions &body labels-body) def-form
(declare (ignore _))
(destructuring-bind (name args &body body) (car definitions)
`(let ((,cache ,cache-form))
(,(car def-form)
((,(make-reset-name name) () ,(make-reset-form cache-type))
(,name ,args
(labels ((,name-alias ,args ,@body))
(declare (inline ,name-alias))
,@(extract-declarations body)
,(make-cache-check-form cache-type args)))
,@(cdr definitions))
(declare (ignorable #',(make-reset-name name)))
,@labels-body))))))))))
;; (test with-memoizing
;; (finishes (macroexpand `(with-memoizing (:hash-table :test #'equal)
;; (defun add (x y) (+ x y)))))
;; (finishes (macroexpand `(with-memoizing (:array '(10 10)
;; :element-type 'fixnum
;; :initial-element -1)
;; (defun add (x y) (+ x y)))))
;; (finishes (macroexpand `(with-memoizing (:array '(10 10)
;; :element-type 'fixnum
;; :initial-element -1)
;; (labels ((add (x y) (+ x y))
;; (my-print (x) (print x)))
;; (add 1 2))))))
(defmacro nlet (name args &body body)
(labels ((ensure-list (x) (if (listp x) x (list x))))
(let ((args (mapcar #'ensure-list args)))
`(labels ((,name ,(mapcar #'car args) ,@body))
(,name ,@(mapcar #'cadr args))))))
(declaim (inline split-ints-into-vector))
(defun split-ints-into-vector (string dest-vector &key (offset 0) (key #'identity))
(declare (string string)
(function key)
((array * (*)) dest-vector)
((integer 0 #.most-positive-fixnum) offset))
(loop with position = 0
for idx from offset below (length dest-vector)
do (setf (values (aref dest-vector idx) position)
(parse-integer string :start position :junk-allowed t))
(setf (aref dest-vector idx) (funcall key (aref dest-vector idx)))
finally (return dest-vector)))
(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)
(defmacro println (obj &optional (stream '*standard-output*))
`(let ((*read-default-float-format* 'double-float))
(prog1 (princ ,obj ,stream) (terpri ,stream))))
(defconstant +mod+ 1000000007)
;; Hauptteil
(defun solve (bs)
(declare #.OPT ((simple-array uint32 (*)) bs))
(let ((n+1 (- (length bs) 1)))
(with-memoizing (:array (2002 2002) :element-type 'uint32 :initial-element #xffffffff)
(nlet recurse ((x 0) (y 1))
(cond ((or (= x n+1) (= y n+1))
(abs (- (aref bs x) (aref bs y))))
((< x y) ; X's turn
(loop for x from (1+ y) to n+1
maximize (recurse x y)))
((> x y) ; Y's turn
(loop for y from (1+ x) to n+1
minimize (recurse x y)))
(t (error "Huh?")))))))
(defun main ()
(declare #.OPT)
(let* ((n (read))
(z (read))
(w (read))
(bs (make-array (+ n 2) :element-type 'uint32)))
(split-ints-into-vector (read-line) bs :offset 2)
(setf (aref bs 0) z
(aref bs 1) w)
(println (solve bs))))
#-swank(main)
Submission Info
| Submission Time |
|
| Task |
D - ABS |
| User |
sansaqua |
| Language |
Common Lisp (SBCL 1.1.14) |
| Score |
0 |
| Code Size |
8937 Byte |
| Status |
TLE |
| Exec Time |
2104 ms |
| Memory |
45284 KiB |
Judge Result
| Set Name |
Sample |
All |
| Score / Max Score |
0 / 0 |
0 / 500 |
| Status |
|
|
| Set Name |
Test Cases |
| Sample |
example_0, example_1, example_2, example_3 |
| All |
example_0, example_1, example_2, example_3, one_0, one_1, one_2, one_3, one_4, one_5, one_6, one_7, rand_0, rand_1, rand_10, rand_11, rand_12, rand_13, rand_14, rand_15, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9 |
| Case Name |
Status |
Exec Time |
Memory |
| example_0 |
AC |
248 ms |
45284 KiB |
| example_1 |
AC |
85 ms |
33252 KiB |
| example_2 |
AC |
84 ms |
33252 KiB |
| example_3 |
AC |
84 ms |
33248 KiB |
| one_0 |
AC |
84 ms |
33248 KiB |
| one_1 |
AC |
84 ms |
33252 KiB |
| one_2 |
AC |
85 ms |
33256 KiB |
| one_3 |
AC |
84 ms |
33252 KiB |
| one_4 |
AC |
84 ms |
33252 KiB |
| one_5 |
AC |
84 ms |
33248 KiB |
| one_6 |
AC |
84 ms |
33252 KiB |
| one_7 |
AC |
84 ms |
33252 KiB |
| rand_0 |
TLE |
2104 ms |
33252 KiB |
| rand_1 |
AC |
682 ms |
33248 KiB |
| rand_10 |
TLE |
2104 ms |
33252 KiB |
| rand_11 |
AC |
1466 ms |
33252 KiB |
| rand_12 |
TLE |
2104 ms |
33256 KiB |
| rand_13 |
TLE |
2104 ms |
33256 KiB |
| rand_14 |
TLE |
2104 ms |
33248 KiB |
| rand_15 |
AC |
99 ms |
33252 KiB |
| rand_2 |
TLE |
2104 ms |
33248 KiB |
| rand_3 |
TLE |
2104 ms |
33252 KiB |
| rand_4 |
TLE |
2104 ms |
33252 KiB |
| rand_5 |
TLE |
2104 ms |
33252 KiB |
| rand_6 |
TLE |
2104 ms |
33256 KiB |
| rand_7 |
TLE |
2104 ms |
33252 KiB |
| rand_8 |
TLE |
2104 ms |
33248 KiB |
| rand_9 |
TLE |
2104 ms |
33248 KiB |