// Ruudukko
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <set>
#include <vector>
#if HAVE_TESTS
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include <doctest.h>
#endif
using namespace std;
using pint = ptrdiff_t;
template <typename T>
struct span {
T* data;
int size;
T* begin()
{
return data;
}
T* end()
{
return data + size;
}
T& operator[](int i)
{
return *(data + i);
}
const T& operator[](int i) const
{
return *(data + i);
}
};
template <typename T>
struct sqvector {
sqvector(int _n) : vec(_n * _n), n(_n) {}
T& operator()(int row, int col)
{
return vec[row * n + col];
}
const T& operator()(int row, int col) const
{
return vec[row * n + col];
}
span<T> row(int r)
{
return {vec.data() + r * n, n};
}
struct column {
sqvector* vec;
int col;
struct iterator {
column* c{};
int i{};
T& operator*()
{
return c->vec->operator()(i, c->col);
}
const T& operator*() const
{
return c->vec->operator()(i, c->col);
}
iterator& operator++()
{
++i;
return *this;
}
iterator operator++(int)
{
auto tmp(*this);
operator++();
return tmp;
}
iterator operator+(int n)
{
return {c, i + n};
}
bool operator==(const iterator& o) const
{
return c == o.c && i == o.i;
}
bool operator!=(const iterator& o) const
{
return !operator==(o);
}
};
iterator begin()
{
return iterator{this, 0};
}
iterator end()
{
return iterator{this, vec->n};
}
};
column col(int c)
{
return column{this, c};
}
void fold()
{
/*
* 1 2 3 _
* 4 5 _ x
* 6 _ x x
* _ x x x
* ->
* 1 2 3 _
* 4 5 _ 3
* 6 _ 5 4
* _ 6 2 1
*/
}
vector<T> vec;
int n;
};
template <typename It, typename T>
void iota_dec(It f, It l, T v)
{
while (f != l) {
*f++ = v;
--v;
}
}
#if !HAVE_TESTS
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
sqvector<int> vec(n);
if (n == 1) {
cout << "1\n";
return 0;
}
// top and bottom row
iota(vec.row(0).begin(), vec.row(0).end(), 1);
// iota_dec(vec.row(n - 1).begin(), vec.row(n - 1).end(), n);
// left and right column
{
auto col = vec.col(0);
iota(col.begin(), col.end(), 1);
// col = vec.col(n - 1);
// iota_dec(col.begin(), col.end(), n);
}
// diagonals
// skip corners, they're already set
{
for (int i = 1; i != n - 1; ++i) {
// top-right -> bottom-left all ns
// vec(i, n - i - 1) = n;
// top-left -> bottom-right all 1s
vec(i, i) = 1;
}
}
// if (n <= 4) {
// if n <= 4, we're done
// return 0;
//}
set<int> nums{};
for (int i = 1; i <= n * 4; ++i) {
nums.insert(i);
}
// check for 0s
set<int> cache{};
vector<int> vcache{};
for (int i = 1; i != n; ++i) {
auto row = vec.row(i);
for (int j = 0; j != n; ++j) {
if (row[j] == 0) {
// 0 found in (i,j)
for (auto it = row.begin(); it != row.begin() + j; ++it) {
cache.insert(*it);
}
{
auto col = vec.col(j);
for (auto it = col.begin(); it != col.begin() + i; ++it) {
cache.insert(*it);
}
}
set_difference(nums.begin(), nums.end(), cache.begin(),
cache.end(), back_inserter(vcache));
int val = vcache.front();
// printf("For cell (%d, %d), trying %d\n", i, j, val);
cache.clear();
vcache.clear();
row[j] = val;
#if 0
// find minmax to the left
auto l_minmax = minmax_element(row.begin(), row.begin() + j);
// find minxmax above
auto col = vec.col(j);
auto t_minmax = minmax_element(col.begin(), col.begin() + i);
printf(
"For cell (%d, %d), lmin: %d, lmax: %d; tmin: %d, tmax: "
"%d\n",
i, j, *l_minmax.first, *l_minmax.second, *t_minmax.first,
*t_minmax.second);
#endif
}
}
}
// print for debug
for (int i = 0; i != n; ++i) {
for (int j = 0; j != n; ++j) {
cout << vec(i, j) << ' ';
}
cout << '\n';
}
return 0;
}
#else
TEST_CASE("sqvector")
{
sqvector<int> v(4);
v(0, 0) = 1;
CHECK(v(0, 0) == 1);
v.vec[3] = 2;
CHECK(v(0, 3) == 2);
}
#endif
