Codeforces Round #540 (Div. 3) C. Palindromic Matrix 【暴力】 C. Palindromic Matrix

任意门：http://codeforces.com/contest/1118/problem/C

Let's call some square matrix with integer values in its cells palindromic if it doesn't change after the order of rows is reversed and it doesn't change after the order of columns is reversed.

For example, the following matrices are palindromic:

$Codeforces Round #540 (Div. 3) C. Palindromic Matrix 【暴力】 C. Palindromic Matrix$

The following matrices are not palindromic because they change after the order of rows is reversed:

$Codeforces Round #540 (Div. 3) C. Palindromic Matrix 【暴力】 C. Palindromic Matrix$

The following matrices are not palindromic because they change after the order of columns is reversed:

$Codeforces Round #540 (Div. 3) C. Palindromic Matrix 【暴力】 C. Palindromic Matrix$

You are given

Input

The first line contains one integer

The second line contains

Output

If it is possible to put all of the

If it's impossible to construct any matrix, then print "NO".

You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.

Examples

input

Copy

4
1 8 8 1 2 2 2 2 2 2 2 2 1 8 8 1

output

Copy

input

Copy

3
1 1 1 1 1 3 3 3 3

output

Copy

input

Copy

4
1 2 1 9 8 4 3 8 8 3 4 8 9 2 1 1

output

Copy

NO

input

Copy

1
10

output

Copy

YES
10

Note

Note that there exist multiple answers for the first two examples.

题意概括：

用一串序列构造一个回文方阵。

解题思路：

纯暴力。。。蜜汁bug；

做法很显然啊，分奇偶；

N为偶数的情况，直接按照策略四个四个构造即可，不存在解的情况就是出现不能被 4 整除的情况（上下左右要对称嘛）；

N为奇数的情况，首先把最中间那个填了，找出现次数为奇数的数即可。

然后也是先按照策略四个四个构造；

最后在两个两个构造，把中间那个十字部分填满。

想法很simple，bug很崩溃。。。

AC code：

  1 #include <bits/stdc++.h>
  2 #define INF 0x3f3f3f3f
  3 #define LL long long
  4 using namespace std;
  5 const int MAXN = 1e3+10;
  6 int sum[MAXN];
  7 int ans[50][50];
  8 int n, num;
  9 
 10 int main()
 11 {
 12     scanf("%d", &n);
 13     int N = n*n, x;
 14     for(int i = 1; i <= N; i++){
 15         scanf("%d", &x);
 16         sum[x]++;
 17     }
 18     int flag = true;
 19     int mid = (n+1)/2;
 20     int num = 1;
 21     if(n%2 == 0){
 22         for(int i = 1; i <= mid; i++){
 23             for(int j = 1; j <= mid; j++){
 24                 for(; num <= 1000; num++){
 25                     if(sum[num]){
 26                         if(sum[num]%4){
 27                             flag = false;
 28                             break;
 29                         }
 30                         ans[i][j] = ans[i][n-j+1] = ans[n-i+1][j] = ans[n-i+1][n-j+1] = num;
 31                         sum[num]-=4;
 32                         break;
 33                     }
 34                 }
 35                 if(num > 1000) flag = false;
 36                 if(!flag) break;
 37             }
 38             if(!flag) break;
 39         }
 40     }
 41     else{
 42         flag = true;
 43         num = 1;
 44         for(; num <= 1000; num++){
 45             if(sum[num]%2){
 46                 ans[mid][mid] = num;
 47                 sum[num]--;
 48                 break;
 49             }
 50         }
 51         if(num > 1000){
 52             flag = false;
 53             //puts("zjy");
 54         }
 55         else{
 56             num = 1;
 57             for(int i = 1; i < mid; i++){
 58                 for(int j = 1; j < mid; j++){
 59                     for(; num <= 1000; num++){
 60                         if(sum[num] == 0) continue;
 61                         if(sum[num]/4 < 1) continue;
 62                         ans[i][j] = ans[i][n-j+1] = ans[n-i+1][j] = ans[n-i+1][n-j+1] = num;
 63                         sum[num]-=4;
 64                         break;
 65                     }
 66                     if(num > 1000) flag = false;
 67                     if(!flag) break;
 68                 }
 69                 if(!flag) break;
 70             }
 71 
 72             num = 1;
 73             for(int i = 1; i < mid; i++){
 74                 for(; num <= 1000; num++){
 75                     if(sum[num]/2 >= 1){
 76                         ans[mid][i] = ans[mid][n-i+1] = num;
 77                         sum[num]-=2;
 78                         break;
 79                     }
 80                 }
 81                 if(num > 1000){flag = false; break;}
 82             }
 83 
 84             num = 1;
 85             for(int i = 1; i < mid; i++){
 86                 for(; num <= 1000; num++){
 87                     if(sum[num]/2 >= 1){
 88                         ans[i][mid] = ans[n-i+1][mid] = num;
 89                         sum[num]-=2;
 90                         break;
 91                     }
 92                 }
 93                 if(num > 1000){flag = false; break;}
 94             }
 95         }
 96     }
 97 
 98     if(!flag) puts("NO");
 99     else{
100         puts("YES");
101         for(int i = 1; i <= n; i++){
102             for(int j = 1; j <= n; j++)
103                 printf("%d ", ans[i][j]);
104             puts("");
105         }
106     }
107 
108     return 0;
109 }

View Code

Codeforces Round #540 (Div. 3) C. Palindromic Matrix 【暴力】 C. Palindromic Matrix

题意概括：

解题思路：

相关推荐