Submission #5889821


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)))
               (setf (gethash m^hia table) nil)
            finally (println -1)))))

#-swank(main)

Submission Info

Submission Time
Task K - 乱数調整
User sansaqua
Language Common Lisp (SBCL 1.1.14)
Score 300
Code Size 6408 Byte
Status AC
Exec Time 470 ms
Memory 37472 KB

Judge Result

Set Name Subtask All
Score / Max Score 30 / 30 270 / 270
Status
AC × 20
AC × 63
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 94 ms 19176 KB
scrambled_01.txt AC 92 ms 19044 KB
scrambled_02.txt AC 93 ms 19044 KB
scrambled_03.txt AC 154 ms 29284 KB
scrambled_04.txt AC 92 ms 19040 KB
scrambled_05.txt AC 93 ms 19048 KB
scrambled_06.txt AC 92 ms 19040 KB
scrambled_07.txt AC 92 ms 19044 KB
scrambled_08.txt AC 92 ms 19044 KB
scrambled_09.txt AC 92 ms 19048 KB
scrambled_10.txt AC 92 ms 19044 KB
scrambled_11.txt AC 92 ms 19044 KB
scrambled_12.txt AC 92 ms 19044 KB
scrambled_13.txt AC 92 ms 19044 KB
scrambled_14.txt AC 160 ms 31332 KB
scrambled_15.txt AC 160 ms 31332 KB
scrambled_16.txt AC 370 ms 35432 KB
scrambled_17.txt AC 203 ms 33380 KB
scrambled_18.txt AC 115 ms 31332 KB
scrambled_19.txt AC 125 ms 31328 KB
scrambled_20.txt AC 113 ms 31332 KB
scrambled_21.txt AC 116 ms 31332 KB
scrambled_22.txt AC 110 ms 31336 KB
scrambled_23.txt AC 110 ms 31328 KB
scrambled_24.txt AC 137 ms 31332 KB
scrambled_25.txt AC 109 ms 31332 KB
scrambled_26.txt AC 117 ms 31332 KB
scrambled_27.txt AC 124 ms 31336 KB
scrambled_28.txt AC 92 ms 19048 KB
scrambled_29.txt AC 143 ms 31336 KB
scrambled_30.txt AC 92 ms 19040 KB
scrambled_31.txt AC 155 ms 31328 KB
scrambled_32.txt AC 92 ms 19040 KB
scrambled_33.txt AC 92 ms 19040 KB
scrambled_34.txt AC 92 ms 19048 KB
scrambled_35.txt AC 92 ms 19040 KB
scrambled_36.txt AC 93 ms 19040 KB
scrambled_37.txt AC 109 ms 31332 KB
scrambled_38.txt AC 114 ms 31336 KB
scrambled_39.txt AC 168 ms 31332 KB
scrambled_40.txt AC 119 ms 31328 KB
scrambled_41.txt AC 162 ms 31332 KB
scrambled_42.txt AC 131 ms 31332 KB
subtask_00.txt AC 154 ms 29288 KB
subtask_01.txt AC 155 ms 29284 KB
subtask_02.txt AC 470 ms 37472 KB
subtask_03.txt AC 470 ms 37472 KB
subtask_04.txt AC 92 ms 19048 KB
subtask_05.txt AC 92 ms 19048 KB
subtask_06.txt AC 92 ms 19040 KB
subtask_07.txt AC 92 ms 19040 KB
subtask_08.txt AC 92 ms 19040 KB
subtask_09.txt AC 92 ms 19048 KB
subtask_10.txt AC 92 ms 19044 KB
subtask_11.txt AC 92 ms 19048 KB
subtask_12.txt AC 93 ms 19040 KB
subtask_13.txt AC 93 ms 19044 KB
subtask_14.txt AC 92 ms 19040 KB
subtask_15.txt AC 142 ms 29284 KB
subtask_16.txt AC 92 ms 19044 KB
subtask_17.txt AC 147 ms 29284 KB
subtask_18.txt AC 92 ms 19044 KB
subtask_19.txt AC 92 ms 19040 KB