CS Academy - Submission

Common LISP5.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
(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))))
  #+sbcl (setq *random-state* (seed-random-state (nth-value 1 (get-time-of-day)))))
#+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
(defpackage :cp/read-fixnum
  (:use :cl)
  (:export #:read-fixnum))
(in-package :cp/read-fixnum)
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setq minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48)
                              (* 10 (the (integer 0 #.(floor most-positive-fixnum 10))
                                         result))))
              (return (if minus (- result) result))))))))
;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/read-fixnum :cl-user))
(in-package :cl-user)
;;;
;;; Body
;;;
(defun calc (x)
  (ash (* x (+ x 1)) -1))
(defun main ()
  (let* ((n (read))
         (points (make-array n :element-type '(cons int32 int32)))
         stack
         (res 0))
    (dotimes (i n)
      (setf (aref points i) (cons (read-fixnum) (read-fixnum))))
    (setq points (sort points #'< :key #'cdr))
    (loop for p across points
          for (r . c) = p
          do (loop
               (unless stack
                 (push p stack)
                 (return))
               (destructuring-bind (prev-r . prev-c) (car stack)
                 (cond ((<= (+ c r) (+ prev-c prev-r))
                        (return))
                       ((<= (- c r) (- prev-c prev-r))
                        (pop stack))
                       (t (push p stack)
                          (return))))))
    (assert stack)
    (loop for (r . c) in stack
          do (decf res r))
    ;; last
    (destructuring-bind (r . c) (car stack)
      (incf res (calc r)))
    ;; first
    (destructuring-bind ((r . c)) (last stack)
      (incf res (calc r)))
    #>stack
    (loop for (p1 p2) on (reverse stack)
          while p2
          for (r1 . c1) = p1
          for (r2 . c2) = p2
          for mid-r = (max 0 (ceiling (+ (+ r1 r2) (- c1 c2)) 2))
          do (incf res (* mid-r (+ 1 (- c2 c1))))
             (incf res (calc (- r1 mid-r)))
             (incf res (calc (- r2 mid-r))))
    (println res)))
#-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://csacademy.com/contest/virtual36718/task/pyramids/"))
#+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 "30
"
          (run "2
3 1
5 5
" nil)))
  (5am:is
   (equal "4
"
          (run "4
2 2
1 1
1 2
1 3
" nil)))
  (5am:is
   (equal "15
"
          (run "3
3 4
2 1
2 7
" nil))))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Summary
User: palestrina
Verdict: Accepted
Language: Common LISP
CPU Time usage: 182 ms
Memory usage: 12.4 MB
Source code: 5.6 KB
Compilation
Compilation done in 0.01 seconds.
Results
Test Number	CPU Usage	Memory Usage	Result
27	156 ms	12.4 MB	OK
26	179 ms	12.4 MB	OK
25	182 ms	12.4 MB	OK
24	77 ms	10.3 MB	OK
23	57 ms	9764 KB	OK
22	52 ms	9400 KB	OK
21	52 ms	9380 KB	OK
20	49 ms	9244 KB	OK
19	48 ms	9256 KB	OK
18	49 ms	9272 KB	OK
17	51 ms	9268 KB	OK
16	55 ms	9240 KB	OK
15	48 ms	9256 KB	OK
14	60 ms	9256 KB	OK
13	61 ms	9248 KB	OK
12	61 ms	9260 KB	OK
11	60 ms	9260 KB	OK
10	73 ms	9244 KB	OK
9	49 ms	9260 KB	OK
8	48 ms	9352 KB	OK
7	57 ms	9252 KB	OK
6	73 ms	9352 KB	OK
5	61 ms	9240 KB	OK
4	59 ms	9244 KB	OK
3	58 ms	9260 KB	OK
2	60 ms	9240 KB	OK
1	60 ms	9240 KB	OK
0	60 ms	9284 KB	OK