結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712ID 21712
提出日時 2024-12-19 19:10:59
言語 JavaScript
(node v21.7.1)
結果
AC  
実行時間 511 ms / 2,000 ms
コード長 2,930 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 6,692 KB
実行使用メモリ 50,956 KB
最終ジャッジ日時 2024-12-19 19:11:15
合計ジャッジ時間 11,712 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 82 ms
40,320 KB
testcase_01 AC 85 ms
42,836 KB
testcase_02 AC 82 ms
40,192 KB
testcase_03 AC 511 ms
50,508 KB
testcase_04 AC 79 ms
40,064 KB
testcase_05 AC 79 ms
42,712 KB
testcase_06 AC 79 ms
40,192 KB
testcase_07 AC 79 ms
40,064 KB
testcase_08 AC 83 ms
40,448 KB
testcase_09 AC 162 ms
47,964 KB
testcase_10 AC 82 ms
42,588 KB
testcase_11 AC 91 ms
45,184 KB
testcase_12 AC 203 ms
47,836 KB
testcase_13 AC 78 ms
42,456 KB
testcase_14 AC 102 ms
46,336 KB
testcase_15 AC 168 ms
49,876 KB
testcase_16 AC 81 ms
40,064 KB
testcase_17 AC 96 ms
46,464 KB
testcase_18 AC 224 ms
47,992 KB
testcase_19 AC 76 ms
40,320 KB
testcase_20 AC 127 ms
47,872 KB
testcase_21 AC 115 ms
46,464 KB
testcase_22 AC 77 ms
42,452 KB
testcase_23 AC 163 ms
48,000 KB
testcase_24 AC 452 ms
48,664 KB
testcase_25 AC 324 ms
48,664 KB
testcase_26 AC 320 ms
48,916 KB
testcase_27 AC 215 ms
50,700 KB
testcase_28 AC 388 ms
48,656 KB
testcase_29 AC 254 ms
50,832 KB
testcase_30 AC 357 ms
50,828 KB
testcase_31 AC 353 ms
48,660 KB
testcase_32 AC 167 ms
47,880 KB
testcase_33 AC 354 ms
48,784 KB
testcase_34 AC 331 ms
48,920 KB
testcase_35 AC 323 ms
48,788 KB
testcase_36 AC 123 ms
47,964 KB
testcase_37 AC 200 ms
50,956 KB
testcase_38 AC 385 ms
50,700 KB
testcase_39 AC 261 ms
48,920 KB
testcase_40 AC 93 ms
40,320 KB
testcase_41 AC 318 ms
50,820 KB
testcase_42 AC 306 ms
48,660 KB
testcase_43 AC 443 ms
50,700 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

{
	let data = '';
	process.stdin.on('data', (chunk) => { data += chunk; });
	process.stdin.on('end', () => { run(data); });
	process.stdin.setEncoding('utf8');
	process.stdin.resume();
}

function run(data) {
	const input = data.split(/\s+/).map(s => parseInt(s));
	const n = input.shift();
	const k = input.shift();
	const a = new PPuzzle(n).scan(input);
	const b = new PPuzzle(n).scan(input);
	
	const ans = solve(n, k, a, b);
	
	console.log(ans.length);
	ans.map( op => op < n ? `C ${op+1}` : `R ${op+1-n}` )
		.forEach( s => console.log(s) );
}

function solve(n, k, a, b) {
	const ops = [];
	search(b, k, a, ops);
	
	let ans = [];
	let s = a.clone();
	ops.forEach( op => {
		let p;
		if (op < n) {
			p = s.selectCol(op);
			s.operateCol(op);
		} else {
			p = s.selectRow(op-n);
			s.operateRow(op-n);
		}
		const tmp = [];
		let z = op % n;
		for (let cnt = cycle(p)-1; cnt > 0; cnt--) {
			z = p[z];
			tmp.push(op < n ? z : (z+n));
		}
		ans = tmp.concat(ans);
	});
	
	return ans;
}

function search(b, k, t, v) {
	if (k === 0) {
		return t.isSame(b);
	}
	for (let i = 0; i < b.n*2; i++) {
		v.push(i);
		const s = t.clone();
		if (i < b.n) {
			s.operateCol(i);
		} else {
			s.operateRow(i-b.n);
		}
		if (search(b,k-1,s,v)) {
			return true;
		}
		v.pop();
	}
}

function cycle(p) {
	let t = p.slice();
	let w = p.slice();
	for (let cnt = 1; ; cnt++) {
		for (let i = 0; i < p.length; i++) {
			t[p[i]] = w[i];
		}
		let ok = true;
		for (let i = 0; i < p.length; i++) {
			if (p[i] !== t[i]) {
				ok = false;
				break;
			}
		}
		if (ok) {
			return cnt;
		}
		let tmp = t; t = w; w = tmp;
	}
}

class PPuzzle {
	
	constructor(n) {
		this.n = n;
		this.matrix = [];
		this.iCol = [];
		this.iRow = [];
	}
	scan(input) {
		const n =this.n;
		this.matrix = new Array(n).fill(null);
		for (let r = 0; r < n; r++) {
			this.matrix[r] = new Array(n).fill(0);
			for (let c = 0; c < n; c++) {
				this.matrix[r][c] = input.shift() - 1;
			}
		}
		this.iCol = new Array(n).fill(0).map((_,i) => i);
		this.iRow = new Array(n).fill(0).map((_,i) => i);
		return this;
	}
	
	clone() {
		const copied = new PPuzzle(this.n);
		copied.matrix = this.matrix;
		copied.iCol = this.iCol.slice();
		copied.iRow = this.iRow.slice();
		return copied;
	}
	
	at(r, c) {
		return this.matrix[this.iRow[r]][this.iCol[c]];
	}
	
	selectCol(x) {
		return new Array(this.n).fill(0).map((_,r) => this.at(r, x));
	}
	
	selectRow(y) {
		return new Array(this.n).fill(0).map((_,c) => this.at(y, c));
	}
	
	operateCol(x) {
		const p = this.selectCol(x);
		const t = this.iCol.slice();
		p.forEach((v, i) => this.iCol[v] = t[i]);
	}
	
	operateRow(y) {
		const p = this.selectRow(y);
		const t = this.iRow.slice();
		p.forEach((v, i) => this.iRow[v] = t[i]);
	}
	
	isSame(other) {
		for (let r = 0; r < this.n; r++) {
			for (let c = 0; c < this.n; c++) {
				if (this.at(r,c) !== other.at(r,c)) {
					return false;
				}
			}
		}
		return true;
	}
}
0