結果
| 問題 |
No.2803 Bocching Star
|
| コンテスト | |
| ユーザー |
 norioc
|
| 提出日時 | 2025-07-20 19:03:06 |
| 言語 | Scheme (Gauche-0.9.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,364 bytes |
| コンパイル時間 | 519 ms |
| コンパイル使用メモリ | 8,228 KB |
| 実行使用メモリ | 89,200 KB |
| 最終ジャッジ日時 | 2025-07-20 19:04:00 |
| 合計ジャッジ時間 | 52,476 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 22 TLE * 13 |
ソースコード
(use srfi.13) ; string
(use srfi.42) ; list-ec
(use srfi.197) ; chain
(use gauche.array)
(use gauche.collection)
(use gauche.dictionary)
(use gauche.generator)
(use gauche.sequence)
(use scheme.ideque)
(use scheme.list)
(use scheme.set)
(use scheme.sort)
(use util.combinations)
(use util.match)
(use data.queue)
(define (input)
(string-trim-both (read-line)))
(define (ii)
(string->number (input)))
(define (li)
(let ((s (input)))
(map string->number (string-split s " "))))
(define (prn . args)
(for-each-with-index (lambda (i x)
(when (> i 0)
(display " "))
(display x))
args)
(newline))
(define prn* (apply$ prn))
(define (prn-yn b)
(prn (if b "Yes" "No")))
(define-syntax ->/prn
(syntax-rules ()
((_ x fns ...)
(-> x fns ... prn))))
(define-syntax prn/d
(syntax-rules ()
((_ expr ...)
(with-output-to-port (current-error-port)
(^()
(prn expr ...))))))
(define int string->number)
(define str x->string)
(define string* (apply$ string))
(define-method min ((xs <sequence>))
(fold min (~ xs 0) xs))
(define-method max ((xs <sequence>))
(fold max (~ xs 0) xs))
(define (minmax . xs)
(values->list (apply min&max xs)))
(define-method minmax ((xs <sequence>))
(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 gcd* (apply$ gcd))
(define isqrt exact-integer-sqrt)
(define ++ string-append)
(define zip (map$ list))
(define all every)
(define any-ec any?-ec)
(define all-ec every?-ec)
(define concat concatenate)
(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 <sequence>))
(rlet1 dict (make-dict)
(for-each (^x (dict-update! dict x 1+ 0))
xs)))
(define-macro (input! vars . body)
(let ((binds (map (^x
(cond
((symbol? x)
`((,x) (values (ii))))
((list? x)
(if (= 1 (length x))
`(,x (values (li)))
`(,x (apply values (li)))))
(else
(error "symbol or list required, but got:" x))))
vars)))
`(let*-values ,binds
,@body)))
(define-macro (! self quoted-name . args)
(let ((name (cadr quoted-name)))
`(,name ,self ,@args)))
(define-macro (d/ . args)
(let ((ss (map (^(expr)
`(list ,(x->string expr) ,expr))
args)))
`(prn/d (list ,@ss))))
(define mlet match-let)
(define mlet* match-let*)
(define mlet1 match-let1)
(define-macro (mfn pat . body)
(let ((arg (gensym)))
`(lambda (,arg)
(mlet1 ,pat ,arg
,@body))))
(define-syntax count-ec
(syntax-rules ()
((_ qualifiers ...)
(sum-ec qualifiers ... 1))))
(define-method len ((coll <collection>))
(size-of coll))
(define-method len ((deq <ideque>))
(ideque-length deq))
(define (accum xs)
(define (proc a b)
(let1 t (+ a b)
(values t t)))
(map-accum proc 0 xs))
(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 (zip-longest . args)
(let* ((n (apply max (map length args)))
(xxs (map (^(xs)
(append xs (make-list (- n (length xs)) #f)))
args)))
(map (pa$ delete #f)
(apply zip xxs))))
(define (set-from xs)
(apply set eqv-comparator xs))
(define (difference xs ys)
(let ((excludes (set-from ys)))
(filter (^x (not (set-contains? excludes x))) xs)))
;; <hash-table>
(define (make-dict)
(make-hash-table eqv-comparator))
(define-method get ((ht <hash-table>) key :optional (default 0))
(hash-table-get ht key default))
(define-method put! ((ht <hash-table>) key value)
(hash-table-put! ht key value))
(define-method keys ((ht <hash-table>))
(hash-table-keys ht))
(define-method values ((ht <hash-table>))
(hash-table-values ht))
;; <ideque>
(define-method back ((deq <ideque>))
(ideque-back deq))
(define-method append ((deq <ideque>) x)
(ideque-add-back deq x))
(define-method pop ((deq <ideque>))
(ideque-remove-back deq))
(define (slide xs k :key step)
(let ((step (if (undefined? step) k step)))
(let loop ((xs xs)
(res '()))
(if (null? xs)
(reverse res)
(loop (drop* xs step)
(cons (take* xs k) res))))))
(define (slide-strict xs k :key step)
(take-while (^(ys) (= k (len ys)))
(slide xs k :step step)))
(define (unique xs)
(delete-duplicates xs))
(input! ((N S) (P))
(let ((xs (list->vector (sort-by (map-with-index (^(i x) (list x i)) P)
car))))
(let1 res '()
;; 両端
(if (= 1 N)
(push! res 1)
(letrec ((f (^(x y)
(mlet (((a ai) x)
((b bi) y))
(< (+ a S) b)))))
(if-let1 v (f (~ xs 0) (~ xs 1))
(push! res (1+ (cadr (~ xs 0)))))
(if-let1 v (f (~ xs (- N 2)) (~ xs (- N 1)))
(push! res (1+ (cadr (~ xs (- N 1))))))))
(when (> N 2)
(do-ec (: i 1 (1- N))
(mlet (((a ai) (vector-ref xs (1- i)))
((b bi) (vector-ref xs i))
((c ci) (vector-ref xs (1+ i))))
(when (and (< (+ a S) b)
(< (+ b S) c))
(push! res (1+ bi))))))
(sort! res)
(let ((ans (delete-neighbor-dups-squeeze! res)))
(prn (len ans))
(prn* ans)
))))