結果

問題 No.217 魔方陣を作ろう
ユーザー 沙耶花沙耶花
提出日時 2021-11-04 22:21:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,181 bytes
コンパイル時間 4,421 ms
コンパイル使用メモリ 267,480 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-23 05:13:18
合計ジャッジ時間 5,177 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000000000

void p(vector<vector<int>> ans){
	rep(i,ans.size()){
		rep(j,ans[i].size()){
			if(j!=0)cout<<' ';
			cout<<ans[i][j];
		}
		cout<<endl;
	}
}

vector<vector<int>> solve(int n){
	vector<vector<int>> ans(n,vector<int>(n,-1));
	if(n%2==1){
		int y = 0,x = n/2;
		
		rep(i,n*n){			
			if(ans[y][x]!=-1){
				i--;
			}
			else{
				ans[y][x] = i+1;
			}
			y--;
			x++;
			x%=n;
			y%=n;
			if(y<0)y+=n;
			if(ans[y][x]!=-1){
				x--;
				x%=n;
				if(x<0)x+=n;
				y+=2;
				y%=n;
			}
		}
	}
	else if(n%4==0){
		
		rep(i,n){
			rep(j,n){
				ans[i][j] = i*n + j + 1;
			}
		}
		
		rep(i,n/2){
			rep(j,n){
				int x = i%4,y = j%4;
				if(x==0){
					if(y==3||y==0)continue;
				}
				if(x==1){
					if(y==1||y==2)continue;
				}
				if(x==2){
					if(y==1||y==2)continue;
				}
				if(x==3){
					if(y==0||y==3)continue;
				}
				x = i,y = j;
				int xx = n-1-i;
				int yy = n-1-j;
				swap(ans[xx][yy],ans[x][y]);
			}
		}
	}
	else{
		auto temp = solve(n/2);
		
		vector<string> s(temp.size(),string(temp.size(),'.'));
		rep(i,s.size()){
			if(i<=temp.size()/2)s[i] = string(temp.size(),'L');
			else if(i==temp.size()/2+1)s[i] = string(temp.size(),'U');
			else s[i] = string(temp.size(),'X');
		}
		swap(s[temp.size()/2+1][temp.size()/2],s[temp.size()/2][temp.size()/2]);
		rep(i,temp.size()){
			rep(j,temp.size()){
				temp[i][j]--;
				temp[i][j] *= 4;
			}
		}
		
		vector<vector<int>> L = {{4,1},{2,3}};
		vector<vector<int>> U = {{1,4},{2,3}};
		vector<vector<int>> X = {{1,4},{3,2}};
		ans.resize(0);
		rep(i,temp.size()){
			int sz = ans.size();
			ans.push_back(vector<int>());
			ans.push_back(vector<int>());
			rep(j,temp[i].size()){
				vector<vector<int>> aa;
				if(s[i][j]=='L')aa = L;
				else if(s[i][j]=='U')aa = U;
				else aa = X;
				rep(k,2){
					rep(l,2){
						ans[sz+k].push_back(temp[i][j] + aa[k][l]);
					}
				}
			}
		}
			
	}
	return ans;
}

int main(){	
	
	int n;
	cin>>n;
	
	auto ans = solve(n);
	p(ans);
	

	return 0;
	
}
0