結果

問題 No.1072 A Nice XOR Pair
ユーザー norioc
提出日時 2025-08-13 01:07:09
言語 Scheme
(Gauche-0.9.15)
結果
RE  
実行時間 -
コード長 7,925 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 7,712 KB
実行使用メモリ 42,196 KB
最終ジャッジ日時 2025-08-13 01:07:14
合計ジャッジ時間 5,128 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 3 RE * 7
権限があれば一括ダウンロードができます

ソースコード

diff #

(use srfi.13)  ; string
(use srfi.42)  ; list-ec
(use srfi.197) ; chain
(use scheme.list)
(use scheme.vector)
(use data.queue)
(use gauche.dictionary)
(use gauche.generator)
(use gauche.sequence)
(use util.match)

(define input read-line)

(define (read-words)
  (string-split (input) " "))

(define (ii)
  (string->number (input)))

(define (li)
  (map string->number (read-words)))

(define-method prn* ((coll <collection>))
  (for-each-with-index (^(i x)
                         (when (> i 0)
                           (display " "))
                         (display x))
                       coll)
  (newline))

(define (prn . args)
  (prn* args))

(define (prn-yn b)
  (prn (if b "Yes" "No")))

(define-syntax ->/prn
  (syntax-rules ()
    ((_ x fns ...)
     (-> x fns ... prn))))

(define-syntax let/g
  (syntax-rules ()
    ((_ var body ...)
     (generate (lambda (var) body ...)))))

(define-method reverse ((s <string>))
  (string-reverse s))

(define-method reverse ((vs <vector>))
  (rlet1 res (vector-copy vs)
    (vector-reverse! res)))

(define ord char->integer)
(define chr integer->char)

(define int string->number)
(define str x->string)

(define-method min ((xs <collection>))
  (fold min (~ xs 0) xs))
(define-method max ((xs <collection>))
  (fold max (~ xs 0) xs))

(define (minmax . xs)
  (values->list (apply min&max xs)))
(define-method minmax ((xs <collection>))
  (values->list (apply min&max xs)))

(define (sum xs)
  (fold + 0 xs))

(define (divmod a b)
  (values->list (div-and-mod a b)))

(define (ceildiv a b)
  (div (+ a (1- b)) b))

(define (1+ n) (+ n 1))
(define (1- n) (- n 1))
(define (!= a b) (not (= a b)))
(define (midpoint a b) (div (+ a b) 2))

(define pow
  (case-lambda
   ((a b) (expt a b))
   ((a b m) (expt-mod a b m))))

(define sq square)
(define isqrt exact-integer-sqrt)

(define pos? positive?)
(define neg? negative?)
(define == equal?)

(define (cmp< a b) (< (compare a b) 0))
(define (cmp> a b) (> (compare a b) 0))
(define (cmp= a b) (= (compare a b) 0))

(define ++ string-append)

(define all every)
(define any-ec any?-ec)
(define all-ec every?-ec)
(define concat concatenate)
(define foldl fold-left)

(define (pairwise xs)
  (zip xs (cdr xs)))

(define (comb n k)
  (if (or (< k 0) (> k n))
      0
      (let loop ((i 0)
                 (x 1))
        (if (= i k)
            x
            (loop (1+ i) (div (* x (- n i)) (1+ i)))))))

(define-method frequencies ((xs <collection>))
  (let1 ht (make-hash-table equal-comparator)
    (for-each (^x (hash-table-update! ht x 1+ 0)) xs)
    (new ht)))

;; '(a b c) -> op(op(op(init, a), b), c)
(define (scanl op init xs)
  (define (f a b)
    (let1 t (op b a)
      (values t t)))

  (map-accum f init xs))

;; '(a b c) ->  op(a, op(b, op(c, init)))
(define (scanr op init xs)
  (define (f a b)
    (let1 t (op a b)
      (values t t)))

  (reverse (map-accum f init (reverse xs))))

(define zip* (apply$ zip))
(define string* (apply$ string))

(define-macro (input! vars . body)
  (define (group xs)
    (if (null? xs)
      '()
      (let1 x (car xs)
        (cond
         ((keyword? x) ; (:i VAR)
          (assume (and (pair? (cdr xs))
                       (symbol? (cadr xs))))
          (cons (list x (cadr xs)) (group (cddr xs))))
         ((symbol? x)  ; default :i
          (cons (list :i x) (group (cdr xs))))
         ((pair? x)
          (cons (group x) (group (cdr xs))))
         (else
          (error "parse error: " xs))))))

  (define (gen-receive binds body)
    (let* ((ss (gensym))
           (vars (map cadr binds))
           (vals (map-with-index
                  (^(i x)
                    (ecase x
                      ((:i)   `(int (list-ref ,ss ,i)))
                      ((:i-1) `(- (int (list-ref ,ss ,i)) 1))
                      ((:s)   `(list-ref ,ss ,i))))
                  (map car binds))))

      `(receive ,vars (let1 ,ss (read-words)
                        (values ,@vals))
         ,body)))

  (define (gen-receive-list kind var body)
    (let* ((val (ecase kind
                  ((:i)   `(map int (read-words)))
                  ((:i-1) `(map (^x (- (int x) 1)) (read-words)))
                  ((:s)   `(read-words)))))
      `(receive (,var) (values ,val)
         ,body)))

  (define (gen-receive1 kind var body)
    (let* ((val (ecase kind
                  ((:i)   `(int (input)))
                  ((:i-1) `(- (int (input)) 1))
                  ((:s)   `(input)))))
      `(receive (,var) (values ,val)
         ,body)))

  (define (gen binds body)
    (if (null? binds)
      body
      (let1 bind (car binds)
        (if (keyword? (car bind)) ; (:i vAR)
          (gen-receive1 (car bind) (cadr bind) (gen (cdr binds) body))
          (match-let1 (x . more) bind
            (if (null? more)
              (gen-receive-list (car x) (cadr x) (gen (cdr binds) body))
              (gen-receive bind (gen (cdr binds) body))))))))

  (let ((binds (group vars)))
    (gen binds `(begin ,@body))))

(define-macro (! self quoted-name . args)
  (let ((name (cadr quoted-name)))
    `(,name ,self ,@args)))

(define-macro (d/ . args)
  (let ((ss (map (^x
                   `(list (quote ,x) ,x))
                 args)))
    `(pprint (list ,@ss))))

(define mlet match-let)
(define mlet* match-let*)
(define mlet1 match-let1)

(define-macro (mfn pat . body)
  (let ((args (gensym)))
    `(lambda ,args
       (mlet1 ,pat ,args
         ,@body))))

(define-macro (mfn1 pat . body)
  (let ((arg (gensym)))
    `(lambda (,arg)
       (mlet1 ,pat ,arg
         ,@body))))

(define-method len ((coll <collection>))
  (size-of coll))

(define (digits n)
  (map digit->integer (str n)))

(define (digits->int ds)
  (fold-left (^(a b) (+ (* 10 a) b)) 0 ds))

(define (-> x . fns)
  (call-with-values (^() (values x))
    (apply compose (reverse fns))))

(define (rep n thunk)
  (list-ec (: _ n)
           (thunk)))

(define (memoize fn)
  (let1 cache (make-hash-table 'equal?)
    (lambda args
      (if (hash-table-exists? cache args)
        (hash-table-get cache args)
        (rlet1 val (apply fn args)
          (hash-table-put! cache args val))))))

(define (accumulate xs)
  (list->vector (scan-left + 0 xs)))

(define (accum xs)
  (let ((vs (accumulate xs)))
    (case-lambda
     ((l r)  ; [l, r]
      (- (~ vs r) (if (> l 0) (~ vs (1- l)) 0)))
     ((r)    ; [0, r]
      (~ vs r)))))

(define (string->set s)
  (list->set eqv-comparator (string->list s)))

(define (difference xs ys)
  (let ((excludes (list->set equal-comparator ys)))
    (filter (^x (not (set-contains? excludes x))) xs)))

(define (uniq xs)
  (let1 ht (make-hash-table 'equal?)
    (for-each (^x (hash-table-put! ht x #t))
              xs)
    (hash-table-keys ht)))

(define-macro (define-interface class . clauses)
  (let ((self (gensym))
        (kind (gensym))
        (args (gensym)))

    (define (gen-clause kind spec)
      (let1 sym (string->symbol (keyword->string kind))
        `((,sym) ,spec)))

    `(define-method new ((,self ,class))
       (lambda (,kind . ,args)
         (apply (case ,kind
                  ,@(map (^x (gen-clause (car x) (cadr x)))
                         (slices clauses 2)))
                ,self
                ,args)))))

(define-interface <hash-table>
  :get       hash-table-get
  :put!      hash-table-put!
  :update!   hash-table-update!
  :push!     hash-table-push!
  :keys      hash-table-keys
  :values    hash-table-values
  :items     hash-table->alist
  :contains? hash-table-contains?
  :map       hash-table-map)

(define (make-dict)
  (new (make-hash-table equal-comparator)))

(define (alist->dict alist)
  (new (alist->hash-table alist equal-comparator)))


(input! ((N X))
  (let* ((A (rep N ii))
         (freq (frequencies A)))
    (->/prn
     (fold-ec 0
              (: k (freq'keys))
              (:let o (logxor k X))
              (if (< k o))
              (* (freq'get k) (freq'get o))
              +))))
0