#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;
template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
/*
v[x] + v[y] = 1 + e[x][y] (mod 2) for every x, y
e[x][y] = 1 if x and y were initially connected
N variables
N * (N - 1) / 2 equations
-------------------------------------------------
It can be noticed that
if (n - 1) following equations are chosen,
all remaining equations should be able to be determined
v[1] + v[n] = 1 + e[1][n] (mod 2)
...
v[n - 2] + v[n] = 1 + e[n - 1][n] (mod 2)
because
for every 1 <= x < y < n then
we have
v[x] + v[n] = 1 + e[x][n]
v[y] + v[n] = 1 + e[y][n]
=> v[x] + v[y] = 1 + e[x][n] + e[y][n]
this means that,
as long as all remaining equations are consistent with these (n - 1) chosen equations
any solutions of this systems of these (n - 1) equations can be chosen
as solutions of the complete system of n * (n - 1) / 2 equations
(it is obvious that the system of (n - 1) equations should have solutions;
this can be easily proved by substituting one variable and determine remaining variables and check consistency)
*/
constexpr int MAX_N = 102;
int N;
ll result[MAX_N][MAX_N];
signed main() {
#ifdef LOCAL
freopen("input.INP", "r", stdin);
// freopen("output.OUT", "w", stdout);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
cin >> N;
if (N & 1) {
int counter = 0;
fort(x, 1, N) {
fort(y, 1, N)
cout << (++counter) << ' ';
cout << '\n';
}
return 0;
}
if (N == 2) {
/*
The average value is always between two numbers
*/
cout << -1 << '\n';
return 0;
}
int delta = 0;
fort(y, 1, N) {
result[1][y] = y;
delta += y;
}
for (; delta % N; ++delta)
++result[1][N];
/*
"Ceil" up average value
*/
delta = (result[1][N] / N + 1) * N;
fort(y, 1, N) {
fore(x, 2, N) {
result[x][y] = result[x - 1][y] + delta;
result[N][y] += result[x][y];
}
result[N][y] = N * result[N - 1][y] - result[N][y] - result[1][y];
}
fort(x, 1, N) {
fort(y, 1, N)
cout << result[x][y] << ' ';
cout << '\n';
}
// #ifdef LOCAL
// fort(i, 1, N) {
// ll row = 0, column = 0;
// fort(j, 1, N) {
// row += result[i][j];
// column += result[j][i];
// }
// cerr << "Row " << i << ": " << 1.0 * row / N << '\n'
// << "Column " << i << ": " << 1.0 * column / N << '\n';
// }
// #endif // LOCAL
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
