N4 v3

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int, int>
#define pb(x) push_back(x)
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v) {
    for (auto x : v) cout << x << ' ';
    cout << "\n";
}

void cvl(vector <ll> &v) {
    for (auto x : v) cout << x << ' ';
    cout << "\n";
}


void cvv(vector <vector <int> > &v) {
    for (auto x : v) cv(x);
    cout << "\n";
}

void cvb(vector <bool> v) {
    for (bool x : v) cout << x << ' ';
    cout << "\n";
}

void cvs(vector <string>  v) {
    for (auto a : v) {
        cout << a << "\n";
    }
}

void cvp(vector <pii> a) {
    for (auto p : a) {
        cout << p.first << ' ' << p.second << "\n";
    }
    cout << "\n";
}

vector <int> dx, dy;
int n;
vector <vector <int> > m, id;

bool ok1(int i, int j) {
    return i >= 0 && j >= 0 && i + j < n - 1;// && id[i][j] == 0;
}

bool ok2(int i, int j) {
    return i < n && j < n && i + j > n - 1;// && id[i][j] == 0;
}

bool sh = 0;

int main() {
    /*ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);*/
    cin >> n;
    if (n == 1) {
        int x; cin >> x;
        cout << x;
        exit(0);
    }
    dx = { 1, -1, 0, 1,};
    dy = { 0, 1, 1, -1,};
    int i = 0, j = 0;
    m.assign(n, vector <int> (n, 0));
    id.assign(n, vector <int> (n, 0));
    if (sh) {
        cout << "START\n";
        cvv(id);
    }
    if (sh) {
        cout << "PART1\n";
    }
    int cnt = 1;
    id[0][0] = 1;
    int tk = 1;
    while (tk != (n - 1) * n / 2) {
        if (sh) {
            cout << "step1\n";
            cout << "("<<i<<","<<j<<")\n";
        }
        if (ok1(i + dx[0], j + dy[0]) && tk != (n - 1) * n / 2) {
            cnt+=2;
            tk++;
            i = i + dx[0];
            j = j + dy[0];
            id[i][j] = cnt;
        }
        if (sh) {
            cout << "step2\n";
            cout << "("<<i<<","<<j<<")\n";
        }
        while (ok1(i + dx[1], j + dy[1]) && tk != (n - 1) * n / 2) {
            cnt+=2;
            tk++;
            i += dx[1];
            j += dy[1];
            id[i][j] = cnt;
        }
        if (sh) {
            cout << "step3\n";
            cout << "("<<i<<","<<j<<")\n";
        }
        if (ok1(i + dx[2], j + dy[2]) && tk != (n - 1) * n / 2) {
            cnt+=2;
            tk++;
            i += dx[2];
            j += dy[2];
            id[i][j] = cnt;
        }
        if (sh) {
            cout << "step4\n";
            cout << "("<<i<<","<<j<<")\n";
        }
        while (ok1(i + dx[3], j + dy[3]) && tk != (n - 1) * n / 2 ) {
            cnt+=2;
            tk++;
            i += dx[3];
            j += dy[3];
            id[i][j] = cnt;
        }
    }
    if (sh) {
        cvv(id);
    }

    if (sh) {
        cout << "PART 2\n";
    }
    dx = {0, -1, -1, 1};
    dy = {-1, 1, 0, -1};
    cnt = 2;
    tk++;
    id[n-1][n-1] = 2;
    i = n - 1;
    j = n - 1;
    while (tk != (n - 1) * n) {
        if (sh) {
            cout << "step1\n";
            cout << "("<<i<<","<<j<<")\n";
        }
        if (ok2(i + dx[0], j + dy[0]) && tk != (n - 1) * n ) {
            cnt+=2;
            tk++;
            i = i + dx[0];
            j = j + dy[0];
            id[i][j] = cnt;
        }

        if (sh) {
            cout << "step2\n";
            cout << "("<<i<<","<<j<<")\n";
        }
        while (ok2(i + dx[1], j + dy[1]) && tk != (n - 1) * n ) {
            cnt+=2;
            tk++;
            i += dx[1];
            j += dy[1];
            id[i][j] = cnt;
        }
        if (sh) {
            cout << "step3\n";
            cout << "("<<i<<","<<j<<")\n";
        }
        if (ok2(i + dx[2], j + dy[2]) && tk != (n - 1) * n ) {
            cnt+=2;
            tk++;
            i += dx[2];
            j += dy[2];
            id[i][j] = cnt;
        }
        if (sh) {
            cout << "step4\n";
            cout << "("<<i<<","<<j<<")\n";
        }
        while (ok2(i + dx[3], j + dy[3]) && tk != (n - 1) * n ) {
            cnt+=2;
            tk++;
            i += dx[3];
            j += dy[3];
            id[i][j] = cnt;
        }
    }
    if (sh) {
        cvv(id);
    }

    if (sh) {
        cout << "PART3\n";
    }
    cnt++;
    tk++;
    i = 0;
    j = n - 1;
    id[i][j] = cnt;
    while (tk != n * n) {
        cnt++;
        tk++;
        i++;
        j--;
        id[i][j] = cnt;
    }
    if (sh) {
        cvv(id);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> m[i][j];
        }
    }
    vector <int> ans(n*n,0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ans[id[i][j] - 1] = m[i][j];
        }
    }
    cv(ans);
}