#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 200101
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9
using namespace std;
//using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 2> a2;
//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int main()
{
//freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
int a[n][n], u = 1;
for (int i = 0; i < n - 1; i++)
{
set <int> se; se.clear();
ll sm = 0;
int mx = 0;
for (int j = 0; j < n - 1; j++)
{
sm += u;
mx = max(mx, u);
se.insert(u);
a[i][j] = u++;
}
for (; u <= 10000000; u++)
{
if ((sm + u) % n != 0) continue;
int val = (sm + u) / n;
if (val > mx) {cout << -1 << endl; exit(0);}
if (se.find(val) != se.end()) {a[i][n - 1] = u++; break;}
}
}
for (int j = 0; j < n - 1; j++)
{
ll sm = 0;
int mx = 0;
set <int> se; se.clear();
for (int i = 0; i < n - 1; i++) {mx = max(mx, a[i][j]); se.insert(a[i][j]); sm += a[i][j];}
for (; u <= 10000000; u++)
{
if ((sm + u) % n != 0) continue;
int val = (sm + u) / n;
if (val > mx) {cout << -1 << endl; exit(0);}
if (se.find(val) != se.end()) {a[n - 1][j] = u++; break;}
}
}
ll sm = 0, smr = 0;
int mxl = 0, mxr = 0;
set <int> sl, sr; sl.clear(); sr.clear();
for (int i = 0; i < n - 1; i++) {sm += a[i][n - 1]; mxl = max(mxl, a[i][n - 1]); sl.insert(a[i][n - 1]); sr.insert(a[n - 1][i]); mxr = max(mxr, a[n - 1][i]); smr += a[n - 1][i];}
for (; u <= 10000000; u++)
{
if ((sm + u) % n != 0) continue;
if ((smr + u) % n != 0) continue;
int val = (sm + u) / n;
if (val > mxl) {cout << -1 << endl; exit(0);}
val = (smr + u) / n;
if (val > mxr) {cout << -1 << endl; exit(0);}
if (sl.find((sm + u) / n) != sl.end() && sr.find(val) != sr.end()) {a[n - 1][n - 1] = u++; break;}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++) cout << a[i][j] << " ";
cout << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
6 ms |
384 KB |
Output is correct |
8 |
Correct |
7 ms |
384 KB |
Output is correct |
9 |
Correct |
7 ms |
384 KB |
Output is correct |
10 |
Correct |
7 ms |
384 KB |
Output is correct |