Submission #4608658
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
(defmacro buffered-read-line (&optional (buffer-size 30) (in '*standard-input*) (terminate-char #\Space))
"Note that the returned string will be reused."
(let ((buffer (gensym))
(character (gensym))
(idx (gensym)))
`(let ((,buffer (load-time-value (make-string ,buffer-size
:element-type 'base-char))))
(declare (simple-base-string ,buffer))
(loop for ,character of-type base-char =
#-swank (code-char (read-byte ,in nil #.(char-code #\Newline)))
#+swank (read-char ,in nil #\Newline)
for ,idx from 0
until (char= ,character #\Newline)
do (setf (schar ,buffer ,idx) ,character)
finally (when (< ,idx ,buffer-size)
(setf (schar ,buffer ,idx) ,terminate-char))
(return (values ,buffer ,idx))))))
(defmacro split-ints-bind (vars string &body body)
(let ((position (gensym))
(s (gensym)))
(labels ((expand (vars &optional init-pos)
(if (null vars)
body
`((multiple-value-bind (,(car vars) ,position)
(parse-integer ,s :start ,(or init-pos position)
:junk-allowed t)
,@(when (null (cdr vars)) `((declare (ignore ,position))))
,@(expand (cdr vars)))))))
`(let ((,s ,string))
(declare (string ,s))
,@(expand vars 0)))))
(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)
;; 0<=s_i<=p_i (i = 0, ..., n-1)
;; 0<=t_i<=q_i (i = 0, ..., n-1)
;; a_k <= s_(x_k)+t_(y_k) <= b_k (k = 0, ..., m-1)
;; t'_(y_k) := -t_(y_k).
;; 0<=s_i<=p_i (i = 0, ..., n-1)
;; -q_i<=t'_i<=0 (i = 0, ..., n-1)
;; a_k <= s_(x_k)-t'_(y_k) <= b_k (k = 0, ..., m-1)
;; I: start point
;; s_i (t'_i) be the minimal distance from I to the vertex i (n+i).
;; 0-s_i <= 0 (edge from vertex i to I with cost 0)
;; s_i-0 <= p_i (I -> i with cost p_i)
;; 0-t'_i <= q_i (i+n -> I with cost -q_i)
;; t'_i-0 <= 0 (I -> i+n with cost 0)
;; s_(x_k)-t'_(y_k) <= b_k (n+y_k -> x_k with cost b_k)
;; t'_(y_k)-s_(x_k) <= -a_k (x_k -> n+y_k with cost -a_k)
;; This program is feasible iff there is no negative cycle passing through I.
(defun main ()
(declare #.OPT)
(let* ((n (read))
(m (read))
(ps (make-array n :element-type 'uint31))
(qs (make-array n :element-type 'uint31))
(size (1+ (* 2 n)))
;; (to . cost)
(graph (make-array size :element-type 'list :initial-element nil))
(start (- size 1))
(table (make-array size :element-type 'fixnum :initial-element #xffffffff)))
(declare (uint31 n m))
(setf (aref table start) 0)
(split-ints-into-vector (read-line) ps)
(split-ints-into-vector (read-line) qs)
(dotimes (i n)
(push (cons start 0) (aref graph i))
(push (cons i (aref ps i)) (aref graph start))
(push (cons start (aref qs i)) (aref graph (+ i n)))
(push (cons (+ i n) 0) (aref graph start)))
(dotimes (k m)
(split-ints-bind (x y a b) (buffered-read-line)
(declare (uint15 x y)
(uint31 a b))
(decf x) (decf y)
(push (cons x b) (aref graph (+ n y)))
(push (cons (+ n y) (- a)) (aref graph x))))
(dotimes (_ size)
(let (updated-p)
(dotimes (src size)
(let ((current-cost (aref table src)))
(unless (= current-cost #xffffffff)
(dolist (edge (aref graph src))
(let ((dest (car edge))
(cost (+ current-cost (the int32 (cdr edge)))))
(when (< cost (aref table dest))
(setf (aref table dest) cost
updated-p t)))))))
(when (< (aref table start) 0)
(write-line "no")
(return-from main))
(unless updated-p
(write-line "yes")
(return-from main))))
(write-line "yes")))
#-swank(main)
Submission Info
Submission Time |
|
Task |
H - Asteroids2 |
User |
sansaqua |
Language |
Common Lisp (SBCL 1.1.14) |
Score |
200 |
Code Size |
5639 Byte |
Status |
AC |
Exec Time |
180 ms |
Memory |
23016 KB |
Judge Result
Set Name |
All |
Score / Max Score |
200 / 200 |
Status |
|
Set Name |
Test Cases |
All |
00-sample-00, 00-sample-01, 10-small_yes-00, 10-small_yes-01, 10-small_yes-02, 10-small_yes-03, 10-small_yes-04, 10-small_yes-05, 10-small_yes-06, 10-small_yes-07, 10-small_yes-08, 20-small_disturb-00, 20-small_disturb-01, 20-small_disturb-02, 20-small_disturb-03, 20-small_disturb-04, 20-small_disturb-05, 20-small_disturb-06, 20-small_disturb-07, 20-small_disturb-08, 30-large_yes-00, 30-large_yes-01, 30-large_yes-02, 30-large_yes-03, 30-large_yes-04, 40-large_disturb-00, 40-large_disturb-01, 40-large_disturb-02, 40-large_disturb-03, 40-large_disturb-04, 40-large_disturb-05, 40-large_disturb-06, 40-large_disturb-07, 40-large_disturb-08, 40-large_disturb-09, 40-large_disturb-10, 40-large_disturb-11, 40-large_disturb-12, 40-large_disturb-13, 40-large_disturb-14, 40-large_disturb-15 |
Case Name |
Status |
Exec Time |
Memory |
00-sample-00 |
AC |
74 ms |
14820 KB |
00-sample-01 |
AC |
74 ms |
14816 KB |
10-small_yes-00 |
AC |
74 ms |
16872 KB |
10-small_yes-01 |
AC |
74 ms |
16868 KB |
10-small_yes-02 |
AC |
76 ms |
16872 KB |
10-small_yes-03 |
AC |
74 ms |
16872 KB |
10-small_yes-04 |
AC |
74 ms |
16864 KB |
10-small_yes-05 |
AC |
74 ms |
16868 KB |
10-small_yes-06 |
AC |
83 ms |
16868 KB |
10-small_yes-07 |
AC |
83 ms |
16868 KB |
10-small_yes-08 |
AC |
83 ms |
16864 KB |
20-small_disturb-00 |
AC |
75 ms |
16868 KB |
20-small_disturb-01 |
AC |
74 ms |
16868 KB |
20-small_disturb-02 |
AC |
74 ms |
16868 KB |
20-small_disturb-03 |
AC |
74 ms |
16868 KB |
20-small_disturb-04 |
AC |
74 ms |
16864 KB |
20-small_disturb-05 |
AC |
75 ms |
16872 KB |
20-small_disturb-06 |
AC |
83 ms |
16864 KB |
20-small_disturb-07 |
AC |
84 ms |
16868 KB |
20-small_disturb-08 |
AC |
85 ms |
16740 KB |
30-large_yes-00 |
AC |
177 ms |
23012 KB |
30-large_yes-01 |
AC |
180 ms |
23012 KB |
30-large_yes-02 |
AC |
180 ms |
23008 KB |
30-large_yes-03 |
AC |
179 ms |
23008 KB |
30-large_yes-04 |
AC |
178 ms |
23012 KB |
40-large_disturb-00 |
AC |
172 ms |
23012 KB |
40-large_disturb-01 |
AC |
172 ms |
23008 KB |
40-large_disturb-02 |
AC |
172 ms |
23016 KB |
40-large_disturb-03 |
AC |
172 ms |
23016 KB |
40-large_disturb-04 |
AC |
172 ms |
23008 KB |
40-large_disturb-05 |
AC |
171 ms |
23012 KB |
40-large_disturb-06 |
AC |
173 ms |
23016 KB |
40-large_disturb-07 |
AC |
172 ms |
23016 KB |
40-large_disturb-08 |
AC |
172 ms |
23008 KB |
40-large_disturb-09 |
AC |
173 ms |
23012 KB |
40-large_disturb-10 |
AC |
172 ms |
23012 KB |
40-large_disturb-11 |
AC |
173 ms |
23012 KB |
40-large_disturb-12 |
AC |
173 ms |
23012 KB |
40-large_disturb-13 |
AC |
175 ms |
23008 KB |
40-large_disturb-14 |
AC |
173 ms |
23008 KB |
40-large_disturb-15 |
AC |
172 ms |
23016 KB |