結果

問題 No.217 魔方陣を作ろう
ユーザー koyumeishikoyumeishi
提出日時 2015-05-26 23:14:25
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,513 bytes
コンパイル時間 447 ms
コンパイル使用メモリ 73,060 KB
最終ジャッジ日時 2023-09-20 15:13:12
合計ジャッジ時間 798 ms
ジャッジサーバーID
(参考情報)
judge12 / judge14
このコードへのチャレンジ(β)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘std::vector<std::vector<int> > Magic_Square(int)’:
main.cpp:41:3: error: ‘iota’ was not declared in this scope
   iota(tmp.begin(), tmp.end(), 1);
   ^~~~
main.cpp:41:3: note: suggested alternative: ‘int’
   iota(tmp.begin(), tmp.end(), 1);
   ^~~~
   int
main.cpp: In function ‘bool check(std::vector<std::vector<int> >&)’:
main.cpp:99:12: error: ‘accumulate’ was not declared in this scope
  int sum = accumulate(v[0].begin(), v[0].end(),0);
            ^~~~~~~~~~

ソースコード

diff #

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

vector<vector<int>> Magic_Square(int n){

	vector<vector<int>> v(n, vector<int>(n,0));

	if(n&1){	//odd
		int x = n/2;
		int y = 0;
		int cnt = 0;
		v[y][x] = ++cnt;
		while(cnt < n*n){
			x = (x+1)%n;
			y = (y-1+n)%n;
			if(v[y][x] != 0){
				x = (x-1+n)%n;
				y = (y+2)%n;
			}
			v[y][x] = ++cnt;
		}
	}else if(n%4 == 0){	//4k
		int x = 0;
		int y = 0;
		for(int i=0; i<n; i++){
			for(int k=0; k<n/4; k++){
				v[i][(i+k*4)%n] = -1;
				v[i][(3+k*4-i+n)%n] = -1;
			}
		}
		vector<int> tmp(n*n);
		iota(tmp.begin(), tmp.end(), 1);
		set<int> s(tmp.begin(), tmp.end());
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(v[i][j] < 0){
					v[i][j] = i*n + j + 1;
					s.erase(v[i][j]);
				}
			}
		}
		for(int i=n-1; i>=0; i--){
			for(int j=n-1; j>=0; j--){
				if(v[i][j] == 0){
					v[i][j] = *s.begin();
					s.erase(v[i][j]);
				}
			}
		}

	}else{	//4k+2
		auto u = Magic_Square((n-2)/2 + 1);
		for(int i=0; i<u.size(); i++){
			for(int j=0; j<u.size(); j++){
				u[i][j] = (u[i][j] - 1)*4;
			}
		}
		vector<vector<int>> w((n-2)/2+1, vector<int>((n-2)/2 + 1, 0));
		for(int i=0; i<w.size(); i++){
			w[w.size()/2 + 1][i] = 1;
		}
		swap(w[w.size()/2 + 1][w.size()/2], w[w.size()/2][w.size()/2]);

		for(int i=w.size()/2 + 2; i<w.size(); i++){
			for(int j=0; j<w.size(); j++){
				w[i][j] = 2;
			}
		}

		int z[3][2][2] = {
			{{4,1},{2,3}},
			{{1,4},{2,3}},
			{{1,4},{3,2}}
		};

		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				v[i][j] = u[i/2][j/2];
				int w_ = w[i/2][j/2];
				v[i][j] += z[w_][i&1][j&1];
			}
		}
	}


	return v;
}

bool check(vector<vector<int>>& v){
	int sum = accumulate(v[0].begin(), v[0].end(),0);
	for(int i=0; i<v.size(); i++){
		if(sum != accumulate(v[i].begin(), v[i].end(), 0)) return false;
		int sum_r = 0;
		for(int j=0; j<v.size(); j++){
			sum_r += v[j][i];
		}
		if(sum != sum_r) return false;
	}

	int sum_ = 0;
	for(int i=0; i<v.size(); i++){
		sum_ += v[i][i];
	}
	if(sum_ != sum) return false;

	sum_ = 0;

	for(int i=0; i<v.size(); i++){
		sum_ += v[v.size()-1-i][v.size()-1-i];
	}

	if(sum_ != sum) return false;

	return true;
}

int main(){
	int n;
	cin >> n;

	auto v = Magic_Square(n);

	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cout << v[i][j] << " ";
		}
		cout << endl;
	}

	cout << check(v) << endl;;

	return 0;
}
0