fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned long long
  4. #define pii pair<ll, ll>
  5. #define st first
  6. #define nd second
  7. #define file "test"
  8. #define FOR(i,l,r) for (int i=l;i<=r;i++)
  9. #define FOD(i,r,l) for (int i=r;i>=l;i--)
  10. using namespace std;
  11. const ll MOD = 1e9 + 7;
  12. const ll INF = 1e18;
  13. const int N = 64 + 5;
  14.  
  15. int f[N][N];
  16. int n;
  17. void resultError()
  18. {
  19.     cout << "This is not Magic Square!" << "\n";
  20. }
  21. bool mgCheck()
  22. {
  23.     int Val = (n*(n*n+1))/2;
  24.     int sumCol[100], sumRow[100], priA = 0, secA = 0;
  25.     memset(sumCol,0,sizeof(sumCol));
  26.     memset(sumRow,0,sizeof(sumRow));
  27.     FOR(i,0,n-1)
  28.     {
  29.         FOR(j,0,n-1)
  30.         {
  31.             sumRow[i] += f[i][j];
  32.             sumCol[j] += f[i][j];
  33.             if(i == j) priA += f[i][j];
  34.             if(i+j == (n-1)*2) secA += f[i][j];
  35.         }
  36.     }
  37.     FOR(i,0,n-1)
  38.     {
  39.         if(sumRow[i] != Val || sumCol[i] != Val) {resultError(); return 0;}
  40.     }
  41.     if(priA != Val && secA != Val) {resultError(); return 0;}
  42.     return 1;
  43. }
  44. void mgOdd()
  45. {
  46.     int i = 0, j = n >> 1;
  47.     FOR(t,1,n*n)
  48.     {
  49.         f[i][j] = t;
  50.         if(i == 0 && j == n-1) i++;
  51.         else
  52.             i = (i-1+n)%n, j = (j+1)%n;
  53.         if(f[i][j]!=0) i+=2, j-=1;
  54.     }
  55. }
  56.  
  57. //The Magic Square 4n
  58. void mgEven()
  59. {
  60.     int val = 0;
  61.     FOR(i,0,n-1)
  62.     {
  63.         FOR(j,0,n-1)
  64.         {
  65.             val++;
  66.             if(i%4 - j%4 == 0 || i%4 + j%4 == 3) f[i][j] = val;
  67.         }
  68.     }
  69.     val = 0;
  70.     FOD(i,n-1,0)
  71.     {
  72.         FOD(j,n-1,0)
  73.         {
  74.             val++;
  75.             if(!f[i][j]) f[i][j] = val;
  76.         }
  77.     }
  78. }
  79.  
  80. bool typeL(int i, int j, int m)
  81. {
  82.     int sl = n / 4 + 1;
  83.     if(i==m && j==m) return false;
  84.     if(i==m+1 && j == m) return true;
  85.     if(i < sl) return true;
  86.     return false;
  87. }
  88.  
  89. bool typeU(int i, int j, int m)
  90. {
  91.     int sl = n / 4 + 1;
  92.     if(i==m && j == m) return true;
  93.     if(i==sl && j == m) return false;
  94.     if(i==sl) return true;
  95.     return false;
  96. }
  97. const int dx[5] = {-1,0,0,-1};
  98. const int dy[5][5] =
  99. {{0,-1,0,-1},//L
  100. {-1,-1,0,0},//U
  101. {-1,0,-1,0}//X
  102. };
  103. void mgfill(int i, int j, int m, int &val)
  104. {
  105.     int x = i*2 + 1, y = j * 2 + 1;
  106.     /*
  107.         N = 4n + 2
  108.         -> L : n + 1 rows
  109.         -> U : 1 rows
  110.         -> X : n - 1 rows;
  111.     */
  112.  
  113.     //loai L : 0, U : 1, X : 2
  114.     int t = 2;
  115.     if(typeL(i,j,m >> 1)) t = 0;
  116.     else
  117.     if(typeU(i,j,m >> 1)) t = 1;
  118.  
  119.     FOR(i,0,3)
  120.     {
  121.         f[x + dx[i]][y + dy[t][i]] = val;
  122.         val++;
  123.     }
  124. }
  125. //The Magic Square 4n+2
  126. void mgEvenOdd()
  127. {
  128.     int m = n >> 1;
  129.     bool mark[100][100];
  130.  
  131.     memset(mark, 0, sizeof(mark));
  132.  
  133.     int i = 0, j = m >> 1;
  134.     int val = 1;
  135.  
  136.     FOR(t,1,m*m)
  137.     {
  138.         mark[i][j] = 1;
  139.  
  140.         mgfill(i,j,m,val);
  141.  
  142.         if(i == 0 && j == m-1) i++;
  143.         else
  144.             i = (i-1+n)%m, j = (j+1)%m;
  145.  
  146.         if(mark[i][j]!=0) i+=2, j-=1;
  147.     }
  148.  
  149. }
  150. void solve()
  151. {
  152.     cin >> n;
  153.     if(n&1)
  154.         mgOdd();
  155.     if(n%4 == 0)
  156.         mgEven();
  157.     else
  158.         mgEvenOdd();
  159.     if(mgCheck())
  160.     {
  161.         FOR(i,0,n-1)
  162.         {
  163.             FOR(j,0,n-1)
  164.                 cout << f[i][j] << " ";
  165.             cout << "\n";
  166.         }
  167.     }
  168. }
  169. int main()
  170. {
  171.     ios_base::sync_with_stdio(0);
  172.     cin.tie(0); cout.tie(0);
  173.     #ifndef ONLINE_JUDGE
  174. //
  175.     // -> remember change the file name!!! <-
  176. //
  177.         freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
  178.     #endif
  179.     solve();
  180.  
  181.     return 0;
  182. }
  183. /**
  184.   ^ ++
  185.  /O\ ++
  186. |___|
  187. /___\
  188. WMWMW
  189. **/
  190.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
6
stdout
copy 
32 29 4 1 24 21 
30 31 2 3 22 23 
12 9 17 20 28 25 
10 11 18 19 26 27 
13 16 36 33 5 8 
14 15 34 35 6 7
https://ideone.com/WPqpZp
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!