Submission #5889851
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 (progn (ql:quickload '(:cl-debug-print :fiveam)) (shadow :run) (use-package :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) ;; BEGIN_INSERTED_CONTENTS ;; ;; Calculate a^n in O(log(n)) time on any monoids ;; (declaim (inline power)) (defun power (base exponent op identity) "OP := binary operation (on a monoid) IDENTITY := identity element w.r.t. OP" (declare ((unsigned-byte 62) exponent) (function op)) (labels ((recur (x p) (declare ((integer 0 #.most-positive-fixnum) p)) (cond ((zerop p) identity) ((evenp p) (recur (funcall op x x) (ash p -1))) (t (nth-value 0 (funcall op x (recur x (- p 1)))))))) (recur base exponent))) ;;; ;;; Fast operations on GF(2) ;;; (eval-when (:compile-toplevel :load-toplevel :execute) (assert (= sb-vm:n-word-bits 64))) ;; Reference: https://www.pvk.ca/Blog/2014/08/16/how-to-define-new-intrinsics-in-sbcl/ ;; We need to define POPCNT by ourselves as the version of SBCL is 1.1.14 on AtCoder. (sb-c:defknown popcnt ((unsigned-byte 64)) (integer 0 64) (sb-c:foldable sb-c:flushable sb-c:movable sb-c:always-translatable) :overwrite-fndb-silently t) (sb-c:defknown popcnt ((unsigned-byte 64)) (integer 0 64) (sb-c:foldable sb-c:flushable sb-c:movable sb-c:always-translatable) :overwrite-fndb-silently t) (sb-vm::define-vop (popcnt) (:policy :fast-safe) (:translate popcnt) (:args (x :scs (sb-vm::unsigned-reg) :target r)) (:arg-types sb-vm::unsigned-num) (:results (r :scs (sb-vm::unsigned-reg))) (:result-types sb-vm::unsigned-num) (:generator 3 (unless (sb-vm::location= r x) (sb-vm::inst xor r r)) (sb-vm::inst popcnt r x))) (sb-vm::define-vop (popcnt/fx) (:policy :fast-safe) (:translate popcnt) (:args (x :scs (sb-vm::unsigned-reg) :target r)) (:arg-types sb-vm::positive-fixnum) (:results (r :scs (sb-vm::unsigned-reg))) (:result-types sb-vm::unsigned-num) (:generator 2 (unless (sb-vm::location= r x) (sb-vm::inst xor r r)) (sb-vm::inst popcnt r x))) (defun popcnt (x) (popcnt x)) (defun f2-gemm (a b) (declare #.OPT ((simple-array bit (64 64)) a b)) (let* ((tb (make-array 4096 :element-type 'bit)) (c (make-array '(64 64) :element-type 'bit)) (a-storage (array-storage-vector a))) (declare (dynamic-extent tb)) (dotimes (row 64) (let ((tb-index (* row 64))) (dotimes (col 64) (setf (row-major-aref tb (+ tb-index col)) (aref b col row))))) (dotimes (row 64) (dotimes (col 64) (setf (aref c row col) (ldb (byte 1 0) (popcnt (the (unsigned-byte 62) (logand (sb-kernel:%vector-raw-bits a-storage row) (sb-kernel:%vector-raw-bits tb col)))))))) c)) (defun f2-gemv (a v) (declare #.OPT ((simple-array bit (64 64)) a) ((unsigned-byte 62) v)) (let* ((res 0) (a-storage (array-storage-vector a))) (declare ((unsigned-byte 62) res)) (dotimes (row 62) (setf (ldb (byte 1 row) res) (ldb (byte 1 0) (popcnt (logand v (sb-kernel:%vector-raw-bits a-storage row)))))) res)) (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 lfsr (a b n) (dotimes (i n) (format t "~8,'0b ~A~%" a (logbitp 0 a)) (setf a (logxor (ash a -1) (if (logbitp 0 a) b 0))))) (defun main () (declare #.OPT) (let* ((a (read)) (b (read)) (x (read)) (mat (make-array '(64 64) :element-type 'bit :initial-element 0)) (iden (make-array '(64 64) :element-type 'bit :initial-element 0)) (h #.(expt 2 18))) (declare (uint62 a b x)) (loop for j below h for m^ja of-type uint62 = a then (logxor (ash m^ja -1) (if (oddp m^ja) b 0)) when (= m^ja x) do (println j) (return-from main)) (dotimes (i 36) (setf (aref mat i 0) (ldb (byte 1 i) b)) (setf (aref iden i i) 1)) (dotimes (i 35) (setf (aref mat i (+ i 1)) 1)) (let ((table (make-hash-table :size h)) (m^h (power mat h #'f2-gemm iden))) (loop for j below h for m^jx of-type uint62 = x then (logxor (ash m^jx -1) (if (oddp m^jx) b 0)) do (setf (gethash m^jx table) j)) (loop with prev-exp of-type uint62 = 0 with prev-mat = iden for i from 1 to h for m^hia = (f2-gemv m^h a) then (f2-gemv m^h m^hia) ; M^(hi)a for cached-j = (gethash m^hia table) when cached-j do (locally (declare (uint62 cached-j)) (setf prev-mat (f2-gemm prev-mat (power mat (- (- (* h i) cached-j) prev-exp) #'f2-gemm iden))) (setf prev-exp (- (* h i) cached-j)) (when (= x (the uint62 (f2-gemv prev-mat a))) (println (- (* h i) cached-j)) (return-from main))) (remhash m^hia table) finally (println -1))))) #-swank(main)
Submission Info
Submission Time | |
---|---|
Task | K - 乱数調整 |
User | sansaqua |
Language | Common Lisp (SBCL 1.1.14) |
Score | 300 |
Code Size | 6397 Byte |
Status | AC |
Exec Time | 469 ms |
Memory | 37472 KB |
Judge Result
Set Name | Subtask | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 270 / 270 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask | subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt |
All | scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, scrambled_33.txt, scrambled_34.txt, scrambled_35.txt, scrambled_36.txt, scrambled_37.txt, scrambled_38.txt, scrambled_39.txt, scrambled_40.txt, scrambled_41.txt, scrambled_42.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
scrambled_00.txt | AC | 96 ms | 19300 KB |
scrambled_01.txt | AC | 92 ms | 19044 KB |
scrambled_02.txt | AC | 93 ms | 19040 KB |
scrambled_03.txt | AC | 155 ms | 29284 KB |
scrambled_04.txt | AC | 93 ms | 19048 KB |
scrambled_05.txt | AC | 92 ms | 19044 KB |
scrambled_06.txt | AC | 92 ms | 19048 KB |
scrambled_07.txt | AC | 92 ms | 19044 KB |
scrambled_08.txt | AC | 93 ms | 19040 KB |
scrambled_09.txt | AC | 92 ms | 19044 KB |
scrambled_10.txt | AC | 93 ms | 19044 KB |
scrambled_11.txt | AC | 92 ms | 19040 KB |
scrambled_12.txt | AC | 92 ms | 19040 KB |
scrambled_13.txt | AC | 92 ms | 19048 KB |
scrambled_14.txt | AC | 161 ms | 31332 KB |
scrambled_15.txt | AC | 169 ms | 31332 KB |
scrambled_16.txt | AC | 370 ms | 35432 KB |
scrambled_17.txt | AC | 204 ms | 33376 KB |
scrambled_18.txt | AC | 116 ms | 31332 KB |
scrambled_19.txt | AC | 118 ms | 31336 KB |
scrambled_20.txt | AC | 113 ms | 31332 KB |
scrambled_21.txt | AC | 116 ms | 31336 KB |
scrambled_22.txt | AC | 110 ms | 31332 KB |
scrambled_23.txt | AC | 111 ms | 31332 KB |
scrambled_24.txt | AC | 137 ms | 31328 KB |
scrambled_25.txt | AC | 109 ms | 31332 KB |
scrambled_26.txt | AC | 117 ms | 31332 KB |
scrambled_27.txt | AC | 125 ms | 31332 KB |
scrambled_28.txt | AC | 92 ms | 19048 KB |
scrambled_29.txt | AC | 148 ms | 31328 KB |
scrambled_30.txt | AC | 93 ms | 19044 KB |
scrambled_31.txt | AC | 156 ms | 31332 KB |
scrambled_32.txt | AC | 92 ms | 19044 KB |
scrambled_33.txt | AC | 92 ms | 19048 KB |
scrambled_34.txt | AC | 92 ms | 19044 KB |
scrambled_35.txt | AC | 92 ms | 19048 KB |
scrambled_36.txt | AC | 93 ms | 19044 KB |
scrambled_37.txt | AC | 109 ms | 31332 KB |
scrambled_38.txt | AC | 108 ms | 31328 KB |
scrambled_39.txt | AC | 163 ms | 31336 KB |
scrambled_40.txt | AC | 116 ms | 31332 KB |
scrambled_41.txt | AC | 163 ms | 31332 KB |
scrambled_42.txt | AC | 132 ms | 31332 KB |
subtask_00.txt | AC | 155 ms | 29284 KB |
subtask_01.txt | AC | 155 ms | 29280 KB |
subtask_02.txt | AC | 469 ms | 37472 KB |
subtask_03.txt | AC | 469 ms | 37472 KB |
subtask_04.txt | AC | 92 ms | 19040 KB |
subtask_05.txt | AC | 92 ms | 19048 KB |
subtask_06.txt | AC | 92 ms | 19048 KB |
subtask_07.txt | AC | 93 ms | 19040 KB |
subtask_08.txt | AC | 94 ms | 19044 KB |
subtask_09.txt | AC | 93 ms | 19048 KB |
subtask_10.txt | AC | 93 ms | 19040 KB |
subtask_11.txt | AC | 92 ms | 19044 KB |
subtask_12.txt | AC | 93 ms | 19044 KB |
subtask_13.txt | AC | 92 ms | 19040 KB |
subtask_14.txt | AC | 93 ms | 19048 KB |
subtask_15.txt | AC | 147 ms | 29284 KB |
subtask_16.txt | AC | 93 ms | 19044 KB |
subtask_17.txt | AC | 147 ms | 29284 KB |
subtask_18.txt | AC | 93 ms | 19044 KB |
subtask_19.txt | AC | 92 ms | 19044 KB |