結果

問題 No.217 魔方陣を作ろう
ユーザー btkbtk
提出日時 2015-05-27 10:28:09
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,425 bytes
コンパイル時間 665 ms
コンパイル使用メモリ 67,420 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-06 10:35:12
合計ジャッジ時間 1,274 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>


using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

inline void init(int n,VVI &c){
	c.resize(n);
	for(auto &v:c){
		v.resize(n);
		for(auto &u:v)u=0;
	}
}

void twotwo(int n,VVI &c){
	init(n,c);
	int q=n/4;
	for(int i=0;i<q;i++){
		for(int j=0;j<q;j++){
			c[i*4][j*4]=(i*4)*n+(j*4)+1;
			c[i*4][j*4+1]=n*n-((i*4)*n+(j*4+1));
			c[i*4][j*4+2]=n*n-((i*4)*n+(j*4+2));
			c[i*4][j*4+3]=(i*4)*n+(j*4+3)+1;
		}
		for(int j=0;j<q;j++){
			c[i*4+1][j*4]=n*n-((i*4+1)*n+(j*4));
			c[i*4+1][j*4+1]=(i*4+1)*n+(j*4+1)+1;
			c[i*4+1][j*4+2]=(i*4+1)*n+(j*4+2)+1;
			c[i*4+1][j*4+3]=n*n-((i*4+1)*n+(j*4+3));
		}
		for(int j=0;j<q;j++){
			c[i*4+2][j*4]=n*n-((i*4+2)*n+(j*4));
			c[i*4+2][j*4+1]=(i*4+2)*n+(j*4+1)+1;
			c[i*4+2][j*4+2]=(i*4+2)*n+(j*4+2)+1;
			c[i*4+2][j*4+3]=n*n-((i*4+2)*n+(j*4+3));
		}
		for(int j=0;j<q;j++){
			c[i*4+3][j*4]=(i*4+3)*n+(j*4)+1;
			c[i*4+3][j*4+1]=n*n-((i*4+3)*n+(j*4+1));
			c[i*4+3][j*4+2]=n*n-((i*4+3)*n+(j*4+2));
			c[i*4+3][j*4+3]=(i*4+3)*n+(j*4+3)+1;
		}
	}
}

void odd(int n,VVI& c){
	init(n,c);
	int x=0,y=n/2;
	c[x][y]=1;
	for(int i=2;i<=n*n;i++){
		int _x=(x+n-1)%n,_y=(y+1)%n;
		if(c[_x][_y])x=(x+1)%n;
		else x=_x,y=_y;
		c[x][y]=i;
	}
}

void lux(int n,VVI &c){
	int magic[][2][2]={{{4,1},{2,3}},{{1,4},{2,3}},{{1,4},{3,2}}};
	init(n,c);
	VVI mark;
	int half=n/2;
	init(half,mark);
	for(int j=0;j<half;j++)mark[half/2+1][j]=1;
	for(int i=(half/2)+2;i<half;i++)for(int j=0;j<half;j++)mark[i][j]=2;
	mark[half/2][half/2]=1;mark[half/2+1][half/2]=0;
	VVI mini;
	odd(n/2,mini);
	for(int i=0;i<half;i++)
		for(int j=0;j<half;j++){
			mini[i][j]--;mini[i][j]*=4;
			for(int x=0;x<2;x++)
				for(int y=0;y<2;y++)
					c[2*i+x][2*j+y]=mini[i][j]+magic[mark[i][j]][x][y];
		}
}

bool check(int n,VVI &c){
	int num=0;
	int i,j,tmp;
	for(i=0;i<n;i++)
		num+=c[i][i];
	for(i=0,tmp=0;i<n;i++)
		tmp+=c[i][n-1-i];
	if(tmp!=num)return false;
	for(i=0;i<n;i++){
		for(j=0,tmp=0;j<n;j++)
			tmp+=c[i][j];
		if(tmp!=num)return false;
	}
	for(i=0;i<n;i++){
			for(j=0,tmp=0;j<n;j++)
				tmp+=c[j][i];
			if(tmp!=num)return false;
		}
	return true;
}

int main(){
	int n;
	VVI res;
	cin>>n;
	switch(n%4){
	case 2:lux(n,res);break;
	case 0:twotwo(n,res);break;
	default:
	odd(n,res);break;
	}
	for(int i=0;i<n;i++){
		cout<<res[i][0];
		for(int j=1;j<n;j++)cout<<" "<<res[i][j];
		cout<<endl;
	}
	if(check(n,res)==false)cout<<"ERROR"<<endl;
	return 0;
}
0