Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
186
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void initMat(int** mat, int n) {
  6.     int beg = 0;
  7.     for (int i = 0; i < n; i ++) {
  8.         for (int j = 0; j < n; j ++) {
  9.             mat[i][j] = ((beg + j) % n) + 1;
  10.         }
  11.         beg ++;
  12.     }
  13. }
  14.  
  15. void printMat(int** mat, int n) {
  16.     for (int i = 0; i < n; i ++) {
  17.         cout << endl;
  18.         for (int j = 0; j < n; j ++) {
  19.             cout << mat[i][j];
  20.             if (j != n - 1)
  21.                 cout << " ";
  22.         }
  23.     }
  24. }
  25.  
  26. bool initDiag(int* diag, int n, int k) {
  27.  
  28.     for (int i = 0; i < n; i ++){
  29.         diag[i] ++;
  30.         k --;
  31.     }
  32.  
  33.     for (int i = n - 1; i >= 0 && k > 0; i --) {
  34.         while (diag[i] < n && k > 0){
  35.             diag[i] ++;
  36.             k --;
  37.         }
  38.     }
  39.  
  40.  
  41.     bool same = true;
  42.     int tmpVal = diag[0];
  43.     for (int i = 1; i < n - 1; i ++)
  44.         if (tmpVal != diag[i]) {
  45.             same = false;
  46.             break;
  47.         }
  48.     if (same && diag[n-1] != tmpVal) {
  49.         diag[n - 2] ++;
  50.         diag[n - 1] --;
  51.     }
  52.     same = true;
  53.     tmpVal = diag[1];
  54.     for (int i = 1; i < n; i ++){
  55.         if (tmpVal != diag[i]){
  56.             same = false;
  57.             break;
  58.         }
  59.     }
  60.     if (same && diag[0] != tmpVal) {
  61.         diag[0] ++;
  62.         diag[1] --;
  63.     }
  64.    
  65. }
  66.  
  67. void solve(int** mat, int* diag, int n) {
  68.     for (int i = 0; i < n; i ++) {
  69.         int target = diag[i];
  70.         int targetRow = 0;
  71.         for (int j = 0; j < n; j ++) {
  72.             if (mat[j][i] == target){
  73.                 targetRow = j;
  74.                 break;
  75.             }
  76.         }
  77.  
  78.         for (int j = 0; j < n; j ++) {
  79.             int temp = mat[i][j];
  80.             mat[i][j] = mat[targetRow][j];
  81.             mat[targetRow][j] = temp;
  82.         }
  83.  
  84.     }
  85. }
  86.  
  87. int main()
  88. {
  89.     ios::sync_with_stdio(0);
  90.     cin.tie(0);
  91.  
  92.     int t;
  93.     cin >> t;
  94.  
  95.     for (int i = 0; i < t; i ++) {
  96.         int n, k;
  97.         cin >> n >> k;
  98.         if (k < n || k > n*n || k == n + 1 || k == n * n - 1){
  99.             cout << "Case #" << i + 1 << ": IMPOSSIBLE";
  100.             if (i != t - 1)
  101.                 cout << endl;
  102.             continue;
  103.         }
  104.         int** mat;
  105.         mat = new int*[n];
  106.         for (int i = 0; i < n; i ++)
  107.             mat[i] = new int[n];
  108.         for (int i = 0; i < n; i ++)
  109.             for (int j = 0; j < n; j ++)
  110.                 mat[i][j] = 0;
  111.         int diag[n] = {0};
  112.         initMat(mat, n);
  113.         initDiag(diag, n, k);
  114.         solve(mat, diag, n);
  115.  
  116.         cout << "Case #" << i + 1 << ": POSSIBLE";
  117.         printMat(mat, n);
  118.         if (i != t - 1)
  119.             cout << endl;
  120.     }
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement