結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2025-02-17 02:59:21
言語 Scheme
(Gauche-0.9.15)
結果
TLE  
実行時間 -
コード長 2,619 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 7,080 KB
実行使用メモリ 34,436 KB
最終ジャッジ日時 2025-02-17 02:59:27
合計ジャッジ時間 4,672 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3 TLE * 1
other -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff #

#!/usr/bin/env gosh
; (use gauche.collection)
(use gauche.sequence) ; ref for-each-with-index
(use gauche.uvector) ; list->u8vector u8vector-map u8vector= u8vector-copy
(use gauche.array) ; array-ref array-retabulate make-u8array

(define (mref a irow icol r c)
	(array-ref a (ref irow r) (ref icol c)))

(define (select-col a irow icol x)
	(u8vector-map (^r (array-ref a r (ref icol x))) irow))

(define (select-row a irow icol y)
	(u8vector-map (^c (array-ref a (ref irow y) c)) icol))

(define (rotate-indexes indexes perm)
	(let ([v (u8vector-copy indexes)])
	     (for-each-with-index (^(i e)
			(set! (ref v e) (ref indexes i))) perm)
	     v))

(define (findi-map n f)
	(let recur ([i 0]) (if (= i n) #f
	     (let ([r (f i)])
	          (if (boolean r) r (recur (+ i 1)))))))

(define (findi n f) (findi-map n (^i (and (f i) i))))

(define (is-same n b a irow icol)
	(not (findi-map n (^r (findi-map n (^c
		(not (= (array-ref b r c) (mref a irow icol r c)))))))))

(define (make-indexes n) (list->u8vector (iota n)))

(define (search-ops n b k a)
	(let recur ([i 0]
	            [irow (make-indexes n)]
	            [icol (make-indexes n)])
	     (if (= i k) (and (is-same n b a irow icol) '())
	         (findi-map (* 2 n) (^(op)
                (let* ([perm (if (< op n)
                             (select-col a irow icol op)
                             (select-row a irow icol (- op n)))]
                       [irow2 (if (< op n) irow (rotate-indexes irow perm))]
                       [icol2 (if (< op n) (rotate-indexes icol perm) icol)]
                       [ops (recur (+ i 1) irow2 icol2)])
					(and (boolean ops) (cons (cons op perm) ops))))))))

(define (solve n k a b)
	(concatenate (map reverse
		(map (^(opperm)
	 		(let* ([op (car opperm)]
	 		       [perm (cdr opperm)]
	 		       [zz (if (< op n) 0 n)])
	    		(let recur ([z (ref perm (modulo op n))]
	    		            [w (rotate-indexes perm perm)]
	    		            [ops '()])
		           (if (u8vector= w perm) ops
		               (recur (ref perm z)
		                      (rotate-indexes w perm)
		                      (cons (+ z zz) ops))))))
			(reverse (search-ops n b k a))))))

(define (read-matrix n)
	(let ([a (make-u8array (shape 0 n 0 n) 0)])
		(array-retabulate! a (^(i j) (- (read) 1)))
		a))

(define (main args)
	(let* ([n (read)]
	       [k (read)]
	       [a (read-matrix n)]
	       [b (read-matrix n)]
	       [ans (solve n k a b)])
		(print (length ans))
		(for-each (^(op)
      		(if (< op n)
      		    (format #t "C ~D~%" (+ op 1))
      		    (format #t "R ~D~%" (- op n -1))))
          	ans))
	0)
0