結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2024-12-28 13:53:10
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 688 ms / 2,000 ms
コード長 2,114 bytes
コンパイル時間 2,342 ms
コンパイル使用メモリ 157,056 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-28 13:53:24
合計ジャッジ時間 11,998 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.conv, std.range, std.algorithm, std.array;

alias matrix = ulong[][];

auto deepcopy(matrix m) => m.map!(array).array;

void reorderColsByColPerm(matrix s, ulong x)
{
	auto t = s.deepcopy;
	foreach (r; iota(t.length))
	{
		foreach (c; iota(t.length))
		{
			s[ r ][ t[c][x]-1 ] = t[r][c];	
		}
	}
}

void reorderRowsByRowPerm(matrix s, ulong y)
{
	auto t = s.deepcopy;
	foreach (r; iota(t.length))
	{
		foreach (c; iota(t.length))
		{
			s[ t[y][r]-1 ][ c ] = t[r][c];	
		}
	}
}

ulong[] selectCol(matrix s, ulong x)
{
	return s.map!(row => row[x]).array;
}

ulong[] selectRow(matrix s, ulong y)
{
	return s[y].dup;
}

ulong[] solve(ulong n, ulong k, matrix a, matrix b)
{
	auto ops = new ulong[](k);
	search(b, k, a, ops);
	ulong[] ans = [];
	foreach (op; ops)
	{
		auto p = op < n ? selectCol(a, op) : selectRow(a, op-n);
		auto cnt = cycle(p) - 1;
		auto z = op % n;
		auto tmp = new ulong[cnt];
		foreach (i; iota(cnt))
		{
			z = p[z]-1;
			tmp[i] = op < n ? z : (z+n);
		}
		ans = tmp ~ ans;
		if (op < n)
		{
			reorderColsByColPerm(a, op);
		}
		else
		{
			reorderRowsByRowPerm(a, op-n);
		}
	}

	return ans;
}

bool search(matrix b, ulong k, matrix t, ulong[] v)
{
	if (k == 0)
	{
		return t == b;
	}
	foreach (i; iota(b.length*2))
	{
		v[v.length - k] = i;
		auto s = t.deepcopy;
		if (i < b.length)
		{
			reorderColsByColPerm(s, i);
		}
		else
		{
			reorderRowsByRowPerm(s, i-b.length);
		}
		if (search(b, k-1, s, v))
		{
			return true;
		}
	}
	return false;
}

int cycle(ulong[] p)
{
	auto t = p.dup;
	auto w = p.dup;
	for (int cnt = 1; ; cnt++)
	{
		foreach (i, e; zip(iota(p.length), p))
		{
			t[e-1] = w[i]; 
		}
		if (t == p)
		{
			return cnt;
		}
		copy(t, w);
	}
}

void main()
{
	auto readInts() => readln.split.to!(ulong[]);

	auto firstLine = readInts;
	auto n = firstLine[0];
	auto k = firstLine[1];
	auto a = iota(n).map!(_ => readInts).array;
	auto b = iota(n).map!(_ => readInts).array;

	auto ans = solve(n, k, a, b);

	ans.length.writeln;
	foreach (op; ans)
	{
		if (op < n)
		{
			(op+1).writefln!"C %d";
		}
		else
		{
			(op+1-n).writefln!"R %d";
		}
	}
}
0