| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 638880 | 2022-09-07T19:10:25 Z | Alexandruabcde | Gardening (RMI21_gardening) | C++14 | 31 ms | 24668 KB |
#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;
///4 10 6
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);
}
}
}
}
}
vector <vector <int> > ans;
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;
ans.resize(N);
for (auto &it : ans)
it.resize(M);
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;
PII stsus = {0, 0};
PII drjos = {N-1, M-1};
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) {
if (K <= Min_K_Pos + cnt22) {
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) {
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 = 0; i < N; ++ i ) {
for (int j = 0; j < M; ++ j )
cout << ans[i][j] << " ";
cout << '\n';
}
ans.clear();
}
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 | 31 ms | 24444 KB | Correct! Azusa and Laika like the garden :) |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 31 ms | 24444 KB | Correct! Azusa and Laika like the garden :) |
| 2 | Correct | 21 ms | 24292 KB | Correct! Azusa and Laika like the garden :) |
| 3 | Correct | 21 ms | 24372 KB | Correct! Azusa and Laika like the garden :) |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 31 ms | 24444 KB | Correct! Azusa and Laika like the garden :) |
| 2 | Correct | 21 ms | 24292 KB | Correct! Azusa and Laika like the garden :) |
| 3 | Correct | 21 ms | 24372 KB | Correct! Azusa and Laika like the garden :) |
| 4 | Correct | 22 ms | 24276 KB | Correct! Azusa and Laika like the garden :) |
| 5 | Correct | 22 ms | 24404 KB | Correct! Azusa and Laika like the garden :) |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 29 ms | 24344 KB | Correct! Azusa and Laika like the garden :) |
| 2 | Correct | 22 ms | 24304 KB | Correct! Azusa and Laika like the garden :) |
| 3 | Correct | 21 ms | 24428 KB | Correct! Azusa and Laika like the garden :) |
| 4 | Correct | 21 ms | 24396 KB | Correct! Azusa and Laika like the garden :) |
| 5 | Correct | 21 ms | 24404 KB | Correct! Azusa and Laika like the garden :) |
| 6 | Correct | 21 ms | 24404 KB | Correct! Azusa and Laika like the garden :) |
| 7 | Correct | 21 ms | 24424 KB | Correct! Azusa and Laika like the garden :) |
| 8 | Correct | 23 ms | 24276 KB | Correct! Azusa and Laika like the garden :) |
| 9 | Correct | 22 ms | 24316 KB | Correct! Azusa and Laika like the garden :) |
| 10 | Correct | 21 ms | 24432 KB | Correct! Azusa and Laika like the garden :) |
| 11 | Correct | 21 ms | 24404 KB | Correct! Azusa and Laika like the garden :) |
| 12 | Correct | 21 ms | 24348 KB | Correct! Azusa and Laika like the garden :) |
| 13 | Correct | 21 ms | 24324 KB | Correct! Azusa and Laika like the garden :) |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 16 ms | 24192 KB | Correct! Azusa and Laika like the garden :) |
| 2 | Correct | 16 ms | 24216 KB | Correct! Azusa and Laika like the garden :) |
| 3 | Correct | 15 ms | 24148 KB | Correct! Azusa and Laika like the garden :) |
| 4 | Correct | 17 ms | 24296 KB | Correct! Azusa and Laika like the garden :) |
| 5 | Correct | 17 ms | 24268 KB | Correct! Azusa and Laika like the garden :) |
| 6 | Correct | 16 ms | 24216 KB | Correct! Azusa and Laika like the garden :) |
| 7 | Correct | 16 ms | 24168 KB | Correct! Azusa and Laika like the garden :) |
| 8 | Correct | 19 ms | 24148 KB | Correct! Azusa and Laika like the garden :) |
| 9 | Correct | 20 ms | 24276 KB | Correct! Azusa and Laika like the garden :) |
| 10 | Correct | 19 ms | 24148 KB | Correct! Azusa and Laika like the garden :) |
| 11 | Correct | 15 ms | 24188 KB | Correct! Azusa and Laika like the garden :) |
| 12 | Correct | 16 ms | 24212 KB | Correct! Azusa and Laika like the garden :) |
| 13 | Correct | 16 ms | 24148 KB | Correct! Azusa and Laika like the garden :) |
| 14 | Correct | 16 ms | 24276 KB | Correct! Azusa and Laika like the garden :) |
| 15 | Correct | 15 ms | 24148 KB | Correct! Azusa and Laika like the garden :) |
| 16 | Correct | 16 ms | 24168 KB | Correct! Azusa and Laika like the garden :) |
| 17 | Correct | 15 ms | 24208 KB | Correct! Azusa and Laika like the garden :) |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 31 ms | 24444 KB | Correct! Azusa and Laika like the garden :) |
| 2 | Correct | 21 ms | 24292 KB | Correct! Azusa and Laika like the garden :) |
| 3 | Correct | 21 ms | 24372 KB | Correct! Azusa and Laika like the garden :) |
| 4 | Correct | 22 ms | 24276 KB | Correct! Azusa and Laika like the garden :) |
| 5 | Correct | 22 ms | 24404 KB | Correct! Azusa and Laika like the garden :) |
| 6 | Correct | 29 ms | 24344 KB | Correct! Azusa and Laika like the garden :) |
| 7 | Correct | 22 ms | 24304 KB | Correct! Azusa and Laika like the garden :) |
| 8 | Correct | 21 ms | 24428 KB | Correct! Azusa and Laika like the garden :) |
| 9 | Correct | 21 ms | 24396 KB | Correct! Azusa and Laika like the garden :) |
| 10 | Correct | 21 ms | 24404 KB | Correct! Azusa and Laika like the garden :) |
| 11 | Correct | 21 ms | 24404 KB | Correct! Azusa and Laika like the garden :) |
| 12 | Correct | 21 ms | 24424 KB | Correct! Azusa and Laika like the garden :) |
| 13 | Correct | 23 ms | 24276 KB | Correct! Azusa and Laika like the garden :) |
| 14 | Correct | 22 ms | 24316 KB | Correct! Azusa and Laika like the garden :) |
| 15 | Correct | 21 ms | 24432 KB | Correct! Azusa and Laika like the garden :) |
| 16 | Correct | 21 ms | 24404 KB | Correct! Azusa and Laika like the garden :) |
| 17 | Correct | 21 ms | 24348 KB | Correct! Azusa and Laika like the garden :) |
| 18 | Correct | 21 ms | 24324 KB | Correct! Azusa and Laika like the garden :) |
| 19 | Correct | 16 ms | 24192 KB | Correct! Azusa and Laika like the garden :) |
| 20 | Correct | 16 ms | 24216 KB | Correct! Azusa and Laika like the garden :) |
| 21 | Correct | 15 ms | 24148 KB | Correct! Azusa and Laika like the garden :) |
| 22 | Correct | 17 ms | 24296 KB | Correct! Azusa and Laika like the garden :) |
| 23 | Correct | 17 ms | 24268 KB | Correct! Azusa and Laika like the garden :) |
| 24 | Correct | 16 ms | 24216 KB | Correct! Azusa and Laika like the garden :) |
| 25 | Correct | 16 ms | 24168 KB | Correct! Azusa and Laika like the garden :) |
| 26 | Correct | 19 ms | 24148 KB | Correct! Azusa and Laika like the garden :) |
| 27 | Correct | 20 ms | 24276 KB | Correct! Azusa and Laika like the garden :) |
| 28 | Correct | 19 ms | 24148 KB | Correct! Azusa and Laika like the garden :) |
| 29 | Correct | 15 ms | 24188 KB | Correct! Azusa and Laika like the garden :) |
| 30 | Correct | 16 ms | 24212 KB | Correct! Azusa and Laika like the garden :) |
| 31 | Correct | 16 ms | 24148 KB | Correct! Azusa and Laika like the garden :) |
| 32 | Correct | 16 ms | 24276 KB | Correct! Azusa and Laika like the garden :) |
| 33 | Correct | 15 ms | 24148 KB | Correct! Azusa and Laika like the garden :) |
| 34 | Correct | 16 ms | 24168 KB | Correct! Azusa and Laika like the garden :) |
| 35 | Correct | 15 ms | 24208 KB | Correct! Azusa and Laika like the garden :) |
| 36 | Correct | 24 ms | 24532 KB | Correct! Azusa and Laika like the garden :) |
| 37 | Correct | 25 ms | 24588 KB | Correct! Azusa and Laika like the garden :) |
| 38 | Correct | 24 ms | 24532 KB | Correct! Azusa and Laika like the garden :) |
| 39 | Correct | 26 ms | 24616 KB | Correct! Azusa and Laika like the garden :) |
| 40 | Correct | 24 ms | 24600 KB | Correct! Azusa and Laika like the garden :) |
| 41 | Correct | 27 ms | 24524 KB | Correct! Azusa and Laika like the garden :) |
| 42 | Correct | 26 ms | 24568 KB | Correct! Azusa and Laika like the garden :) |
| 43 | Correct | 24 ms | 24588 KB | Correct! Azusa and Laika like the garden :) |
| 44 | Correct | 28 ms | 24596 KB | Correct! Azusa and Laika like the garden :) |
| 45 | Correct | 24 ms | 24552 KB | Correct! Azusa and Laika like the garden :) |
| 46 | Correct | 24 ms | 24512 KB | Correct! Azusa and Laika like the garden :) |
| 47 | Correct | 25 ms | 24604 KB | Correct! Azusa and Laika like the garden :) |
| 48 | Correct | 25 ms | 24596 KB | Correct! Azusa and Laika like the garden :) |
| 49 | Correct | 31 ms | 24544 KB | Correct! Azusa and Laika like the garden :) |
| 50 | Correct | 29 ms | 24528 KB | Correct! Azusa and Laika like the garden :) |
| 51 | Correct | 23 ms | 24532 KB | Correct! Azusa and Laika like the garden :) |
| 52 | Correct | 24 ms | 24600 KB | Correct! Azusa and Laika like the garden :) |
| 53 | Correct | 25 ms | 24660 KB | Correct! Azusa and Laika like the garden :) |
| 54 | Correct | 25 ms | 24520 KB | Correct! Azusa and Laika like the garden :) |
| 55 | Correct | 25 ms | 24532 KB | Correct! Azusa and Laika like the garden :) |
| 56 | Correct | 25 ms | 24552 KB | Correct! Azusa and Laika like the garden :) |
| 57 | Correct | 25 ms | 24548 KB | Correct! Azusa and Laika like the garden :) |
| 58 | Correct | 25 ms | 24548 KB | Correct! Azusa and Laika like the garden :) |
| 59 | Correct | 28 ms | 24668 KB | Correct! Azusa and Laika like the garden :) |
| 60 | Correct | 25 ms | 24564 KB | Correct! Azusa and Laika like the garden :) |