Submission #6405751
Source Code Expand
;; -*- coding: utf-8 -*- (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)) #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t)))) #+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax) #-swank (disable-debugger) ; for CS Academy ;; BEGIN_INSERTED_CONTENTS (declaim (ftype (function * (values fixnum &optional)) read-fixnum)) (defun read-fixnum (&optional (in *standard-input*)) (declare #.OPT) (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 #\-)) (setf 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)))))))) (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))) (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) (declaim (inline println)) (defun println (obj &optional (stream *standard-output*)) (let ((*read-default-float-format* 'double-float)) (prog1 (princ obj stream) (terpri stream)))) (defconstant +mod+ 1000000007) ;; Body (defun feasible-p (as threshold) (declare ((simple-array uint16 (* *)) as) (uint32 threshold)) #>threshold (destructuring-bind (n m) (array-dimensions as) (let ((indices (make-array n :element-type 'uint16 :initial-element 0)) (marked (make-array m :element-type 'bit :initial-element 0)) (table (make-array m :element-type 'uint16))) (labels ((step-index (i) (loop (incf (aref indices i)) (when (>= (aref indices i) m) (return-from feasible-p nil)) (when (zerop (aref marked (aref as i (aref indices i)))) (return))))) (loop (fill table 0) (dotimes (i n) (incf (aref table (aref as i (aref indices i))))) #>indices #>marked #>table (when (loop for x across table always (<= x threshold)) (return-from feasible-p t)) (dotimes (i n) (when (> (aref table (aref as i (aref indices i))) threshold) (setf (aref marked (aref as i (aref indices i))) 1) (step-index i)))))))) (defun main () (let* ((n (read)) (m (read)) (as (make-array (list n m) :element-type 'uint16))) (declare (uint16 n m)) (dotimes (i n) (dotimes (j m) (setf (aref as i j) (- (read-fixnum) 1)))) (sb-int:named-let bisect ((ng 0) (ok (* 2 n))) (if (<= (- ok ng) 1) (println ok) (let ((mid (ash (+ ng ok) -1))) (if (feasible-p as mid) (bisect ng mid) (bisect mid ok))))))) #-swank (main)
Submission Info
Submission Time | |
---|---|
Task | B - Sports Festival |
User | sansaqua |
Language | Common Lisp (SBCL 1.1.14) |
Score | 0 |
Code Size | 4135 Byte |
Status | WA |
Exec Time | 233 ms |
Memory | 26596 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 700 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 233 ms | 26596 KB |
sample_02.txt | AC | 77 ms | 14816 KB |
sample_03.txt | AC | 76 ms | 14824 KB |
subtask_1_01.txt | AC | 76 ms | 14820 KB |
subtask_1_02.txt | AC | 74 ms | 14816 KB |
subtask_1_03.txt | WA | 76 ms | 14820 KB |
subtask_1_04.txt | AC | 77 ms | 14820 KB |
subtask_1_05.txt | AC | 76 ms | 14824 KB |
subtask_1_06.txt | AC | 77 ms | 14816 KB |
subtask_1_07.txt | AC | 81 ms | 14820 KB |
subtask_1_08.txt | AC | 76 ms | 14820 KB |
subtask_1_09.txt | AC | 74 ms | 14816 KB |
subtask_1_10.txt | AC | 75 ms | 14820 KB |
subtask_1_11.txt | WA | 78 ms | 14816 KB |
subtask_1_12.txt | AC | 76 ms | 14816 KB |
subtask_1_13.txt | AC | 77 ms | 14824 KB |
subtask_1_14.txt | AC | 84 ms | 14816 KB |
subtask_1_15.txt | AC | 97 ms | 14816 KB |
subtask_1_16.txt | AC | 86 ms | 14820 KB |
subtask_1_17.txt | AC | 85 ms | 14824 KB |
subtask_1_18.txt | AC | 100 ms | 14824 KB |