結果

問題 No.2984 [Cherry Anniversary 4] 満開の願いを込めた 27 の桜
ユーザー 👑 ygussany
提出日時 2024-12-09 00:19:42
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 64 ms / 4,000 ms
コード長 2,608 bytes
コンパイル時間 1,986 ms
コンパイル使用メモリ 31,744 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-09 00:19:47
合計ジャッジ時間 3,191 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

int next_permutation(int n, int p[])
{
	int i, head, tail = 0;
	static int q[21];
	for (i = n - 2, q[tail++] = p[n-1]; i >= 0; i--) {
		if (p[i] >= p[i+1]) q[tail++] = p[i];
		else break;
	}
	if (i < 0) return 0;
	
	int l = 0, r = tail - 1, m;
	while (l < r) {
		m = (l + r) / 2;
		if (q[m] <= p[i]) l = m + 1;
		else r = m;
	}
	p[i] ^= q[l];
	q[l] ^= p[i];
	p[i] ^= q[l];
	for (i++, head = 0; i < n; i++, head++) p[i] = q[head];
	return 1;
}

void chmin(int *a, int b)
{
	if (*a > b) *a = b;
}

int check(int A[][3][3], int X[][3], int Y[][3], int Z[][3], int p[][3])
{
	int i, j, k, tmp;
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			for (k = 0, tmp = 0; k < 3; k++) tmp += A[p[0][k]][p[1][i]][p[2][j]];
			if (tmp != X[i][j]) return 0;
		}
	}
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			for (k = 0, tmp = 0; k < 3; k++) tmp += A[p[0][i]][p[1][k]][p[2][j]];
			if (tmp != Y[i][j]) return 0;
		}
	}
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			for (k = 0, tmp = 0; k < 3; k++) tmp += A[p[0][i]][p[1][j]][p[2][k]];
			if (tmp != Z[i][j]) return 0;
		}
	}
	return 1;
}

int solve(int A[][3][3], int X[][3], int Y[][3], int Z[][3])
{
	int i, j, p[3][3], ans = 10;
	for (j = 0; j < 3; j++) p[0][j] = j;
	do {
		for (j = 0; j < 3; j++) p[1][j] = j;
		do {
			for (j = 0; j < 3; j++) p[2][j] = j;
			do {
				if (check(A, X, Y, Z, p) != 0) {
					i = 0;
					for (j = 0; j < 3; j++) if (p[0][j] != j) break;
					if (j < 3) {
						i += 2;
						for (j = 0; j < 3; j++) if (p[0][j] == j) break;
						if (j < 3) i--;
					}
					for (j = 0; j < 3; j++) if (p[1][j] != j) break;
					if (j < 3) {
						i += 2;
						for (j = 0; j < 3; j++) if (p[1][j] == j) break;
						if (j < 3) i--;
					}
					for (j = 0; j < 3; j++) if (p[2][j] != j) break;
					if (j < 3) {
						i += 2;
						for (j = 0; j < 3; j++) if (p[2][j] == j) break;
						if (j < 3) i--;
					}
					chmin(&ans, i);
				}
			} while (next_permutation(3, p[2]));
		} while (next_permutation(3, p[1]));
	} while (next_permutation(3, p[0]));
	if (ans == 10) return -1;
	else return ans;
}

int main()
{
	int T, i, j, k, A[3][3][3], X[3][3], Y[3][3], Z[3][3];
	scanf("%d", &T);
	while (T--) {
		for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) for (k = 0; k < 3; k++) scanf("%d", &(A[i][j][k]));
		for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) scanf("%d", &(X[i][j]));
		for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) scanf("%d", &(Y[i][j]));
		for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) scanf("%d", &(Z[i][j]));
		printf("%d\n", solve(A, X, Y, Z));
	}
	fflush(stdout);
	return 0;
}
0