結果

問題 No.2986 Permutation Puzzle
コンテスト
ユーザー ID 21712
提出日時 2024-12-29 03:23:40
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 34 ms / 2,000 ms
コード長 2,184 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 31,872 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-29 03:23:43
合計ジャッジ時間 2,819 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int N, K, ans_len;
int A[100], B[100], ops[4], ans[1000];
int m[4][100], t[100], ct[10], cw[10], p[10];

void reorder_cols_by_col_perm(int *s, int x) {
	memmove(t, s, N*N*sizeof(int));
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			s[ r*N + (t[c*N + x]-1) ] = t[ r*N + c ];
}

void reorder_rows_by_row_perm(int *s, int y) {
	memmove(t, s, N*N*sizeof(int));
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			s[ (t[y*N + r]-1)*N + c ] = t[ r*N + c ];
}

void select_col(int *s, int x) {
	for (int r = 0; r < N; r++)
		p[r] = s[r*N+x];
}

void select_row(int *s, int y) {
	for (int c = 0; c < N; c++)
		p[c] = s[y*N+c];
}

int search(int k, int *z) {
	if (k == 0) {
		return memcmp(z, B, N*N*sizeof(int)) == 0;
	}
	for (int i = 0; i < N*2; i++) {
		ops[K-k] = i;
		memmove(m[k-1], z, N*N*sizeof(int));
		if (i < N) {
			reorder_cols_by_col_perm(m[k-1], i);
		} else {
			reorder_rows_by_row_perm(m[k-1], i-N);
		}
		if (search(k-1, m[k-1])) {
			return -1;
		}
	}
	return 0;
}

int cycle() {
	memmove(cw, p, N*sizeof(int));
	for (int cnt = 1; ; cnt++) {
		for (int i = 0; i < N; i++) {
			ct[p[i]-1] = cw[i];
		}
		if (memcmp(ct, p, N*sizeof(int)) == 0) {
			return cnt;
		}
		memmove(cw, ct, N*sizeof(int));
	}
}

void solve() {
	search(K, A);
	ans_len = 0;
	for (int i = 0; i < K; i++) {
		int op = ops[i];
		if (op < N) {
			select_col(A, op);
		} else {
			select_row(A, op-N);
		}
		int cnt = cycle() - 1;
		memmove(ans + cnt, ans, ans_len*sizeof(int));
		ans_len += cnt;
		int z = op % N;
		for (int e = 0; e < cnt; e++) {
			z = p[z] - 1;
			ans[e] = op < N ? z : (z+N);
		}
		if (op < N) {
			reorder_cols_by_col_perm(A, op);
		} else {
			reorder_rows_by_row_perm(A, op-N);
		}
	}
}

int main() {
	scanf("%d%d",&N,&K);
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			scanf("%d", &A[r*N+c]);
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			scanf("%d", &B[r*N+c]);
	
	solve();
	
	printf("%d\n", ans_len);
	for (int i = 0; i < ans_len; i++) {
		int op = ans[i];
		if (op < N) {
			printf("C %d\n", op+1);
		} else {
			printf("R %d\n", op+1-N);
		}
	}
	
	return 0;
}
0