#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
typedef pair <int, int> PII;
typedef pair <int, pair <int, int> > PIII;
constexpr int NMAX = 1005;
int N, M, K;
/*
vector <PIII> Values[NMAX][NMAX];
void Precompute () {
for (int i = 2; i <= N; i += 2) {
for (int j = 2; j <= M; j += 2) {
if (i == 2) {
Values[i][j].push_back({j/2, {0, 0}});
continue;
}
if (j == 2) {
Values[i][j].push_back({i/2, {0, 0}});
continue;
}
vector <PIII> aux;
for (auto it : Values[i-2][j-2]) {
aux.push_back({it.first + 1, {i-2, j-2}});
}
for (auto it : Values[i-2][j]) {
aux.push_back({it.first + j/2, {i-2, j}});
}
for (auto it : Values[i][j-2]) {
aux.push_back({it.first + i/2, {i, j-2}});
}
sort(aux.begin(), aux.end());
for (auto it : aux) {
if (Values[i][j].empty() || Values[i][j].back().first != it.first)
Values[i][j].push_back(it);
if (!Values[i][j].empty() && Values[i][j].back().first == it.first) {
Values[i][j].pop_back();
Values[i][j].push_back(it);
}
}
}
}
}
*/
int ans[NMAX][NMAX];
void Complete_Border (PII &stsus, PII &drjos, int &who) {
for (int i = stsus.first; i <= drjos.first; ++ i )
ans[i][stsus.second] = ans[i][drjos.second] = who;
for (int i = stsus.second ; i <= drjos.second; ++ i )
ans[stsus.first][i] = ans[drjos.first][i] = who;
++ who;
stsus.first ++, stsus.second ++;
drjos.first --, drjos.second --;
}
void Complete_Column (PII &stsus, PII &drjos, int &who) {
for (int i = stsus.first; i < drjos.first; i += 2) {
ans[i][drjos.second] = ans[i+1][drjos.second] = who;
ans[i][drjos.second-1] = ans[i+1][drjos.second-1] = who;
++ who;
}
drjos.second -= 2;
}
void Complete_Line (PII &stsus, PII &drjos, int who) {
for (int i = stsus.second; i < drjos.second; i += 2) {
ans[drjos.first][i] = ans[drjos.first][i+1] = who;
ans[drjos.first-1][i] = ans[drjos.first-1][i+1] = who;
++ who;
}
drjos.first -= 2;
}
void Do_Testcase() {
cin >> N >> M >> K;
if (N % 2 == 1 || M % 2 == 1) {
cout << "NO\n";
return;
}
int Min_K_Pos = max(N, M) / 2;
int Max_K_Pos = N * M / 4;
if (K < Min_K_Pos || K > Max_K_Pos || (K == Min_K_Pos + 1 && N == M) || K == Max_K_Pos - 1) {
cout << "NO\n";
return;
}
cout << "YES\n";
int who = 1;
for (int i = 1; i <= N; ++ i )
for (int j = 1; j <= M; ++ j )
ans[i][j] = 0;
PII stsus = {1, 1};
PII drjos = {N, M};
int NrLin = N, NrCol = M;
while (NrLin > 2 && NrCol > 2) {
int Min_K_Pos = max(NrLin, NrCol) / 2;
int cnt22 = min(NrLin, NrCol) / 2 - 1;
int cnt20 = (NrLin - NrCol) / 2 + 1;
if (NrLin == NrCol || NrCol > NrLin + 2) {
if (K <= Min_K_Pos + cnt22 - 1) {
Complete_Border(stsus, drjos, who);
-- K;
}
else {
Complete_Column(stsus, drjos, who);
K -= (NrLin / 2);
}
}
else {
if (NrCol == NrLin + 2) {
if (K <= Min_K_Pos + cnt22 - 1 || K == Min_K_Pos + cnt22 + 1) {
Complete_Border(stsus, drjos, who);
-- K;
}
else {
Complete_Column(stsus, drjos, who);
K -= (NrLin / 2);
}
}
else {
if (NrLin == NrCol + 2) {
if (K <= Min_K_Pos + cnt22 - 1 || K == Min_K_Pos + cnt22 + 1) {
Complete_Border(stsus, drjos, who);
-- K;
}
else {
if (K == Min_K_Pos + cnt22) {
Complete_Line(stsus, drjos, who);
K -= (NrCol / 2);
}
else {
Complete_Column(stsus, drjos, who);
K -= (NrLin / 2);
}
}
}
else {
if (K <= Min_K_Pos + cnt22 - 1) {
Complete_Border(stsus, drjos, who);
-- K;
}
else if (K <= Min_K_Pos + cnt22 + cnt20 - 1) {
Complete_Line(stsus, drjos, who);
K -= (NrCol / 2);
}
else {
Complete_Column(stsus, drjos, who);
K -= (NrLin / 2);
}
}
}
}
NrLin = drjos.first - stsus.first + 1;
NrCol = drjos.second - stsus.second + 1;
}
if (NrLin == 2) {
Complete_Line(stsus, drjos, who);
}
else Complete_Column(stsus, drjos, who);
for (int i = 1; i <= N; ++ i ) {
for (int j = 1; j <= M; ++ j )
cout << ans[i][j] << " ";
cout << '\n';
}
}
void Solve () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (; T; -- T )
Do_Testcase();
}
int main () {
if (!DEBUG) {
Solve();
return 0;
}
cin >> N >> M;
/*
Precompute();
for (auto it : Values[N][M]) {
int cnt = it.first;
int i = it.second.first;
int j = it.second.second;
cout << cnt << " " << i << " " << j << '\n';
}
*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
852 KB |
Correct! Azusa and Laika like the garden :) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
852 KB |
Correct! Azusa and Laika like the garden :) |
| 2 |
Correct |
10 ms |
596 KB |
Correct! Azusa and Laika like the garden :) |
| 3 |
Correct |
11 ms |
568 KB |
Correct! Azusa and Laika like the garden :) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
852 KB |
Correct! Azusa and Laika like the garden :) |
| 2 |
Correct |
10 ms |
596 KB |
Correct! Azusa and Laika like the garden :) |
| 3 |
Correct |
11 ms |
568 KB |
Correct! Azusa and Laika like the garden :) |
| 4 |
Failed |
10 ms |
596 KB |
Output does not contain all values between 1 and k |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
12 ms |
852 KB |
Output does not contain all values between 1 and k |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
5 ms |
596 KB |
Output does not contain all values between 1 and k |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
852 KB |
Correct! Azusa and Laika like the garden :) |
| 2 |
Correct |
10 ms |
596 KB |
Correct! Azusa and Laika like the garden :) |
| 3 |
Correct |
11 ms |
568 KB |
Correct! Azusa and Laika like the garden :) |
| 4 |
Failed |
10 ms |
596 KB |
Output does not contain all values between 1 and k |
| 5 |
Halted |
0 ms |
0 KB |
- |
