結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2025-02-17 03:53:30
言語 Scheme
(Gauche-0.9.15)
結果
TLE  
実行時間 -
コード長 2,587 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 6,948 KB
実行使用メモリ 32,292 KB
最終ジャッジ日時 2025-02-17 03:53:34
合計ジャッジ時間 4,759 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
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 (u8vector-ref irow r) (u8vector-ref icol c)))

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

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

(define (rotate-indexes indexes perm)
	(let ([v (u8vector-copy indexes)])
	     (for-each-with-index (^(i e)
			(u8vector-set! v e (u8vector-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 (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)]
	            [ops '()])
	     (if (= i k) (and (is-same n b a irow icol) ops)
	         (findi-map (* 2 n) (^(op)
	            (if (< op n)
	                (let* ([perm (select-col a irow icol op)]
						   [icol2 (rotate-indexes icol perm)])
	                    (recur (+ i 1) irow icol2 (cons (cons op perm) ops)))
	                (let* ([perm (select-row a irow icol (- op n))]
	                       [irow2 (rotate-indexes irow perm)])
						(recur (+ i 1) irow2 icol (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))))))
			(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