結果
問題 |
No.2986 Permutation Puzzle
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }