Submission #1219237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219237		arbuzick	Gardening (RMI21_gardening)	C++20	100 / 100	11 ms	840 KiB

Main

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    if (n % 2 != 0 || m % 2 != 0 || k > n * m / 4 || k == n * m / 4 - 1 || k < max(n, m) / 2) {
        cout << "NO\n";
        return;
    }
    int cnt_nw = (n / 2) * (m / 2);
    vector<vector<int>> ans(n, vector<int>(m, -1));
    int c_nw = 0;
    int n_nw = n, m_nw = m;
    while (true) {
        int cnt_nw = c_nw + (n_nw / 2) * (m_nw / 2);
        if (cnt_nw == k) {
            int col_nw = c_nw;
            for (int i = 0; i < n_nw; i += 2) {
                for (int j = 0; j < m_nw; j += 2) {
                    ans[c_nw + i][c_nw + j] = ans[c_nw + i][c_nw + j + 1] = ans[c_nw + i + 1][c_nw + j] = ans[c_nw + i + 1][c_nw + j + 1] = col_nw;
                    col_nw++;
                }
            }
            c_nw = k;
            break;
        }
        int cnt_nxt = c_nw + 1 + ((n_nw - 2) / 2) * ((m_nw - 2) / 2);
        if (cnt_nxt < k || cnt_nxt == k + 1) {
            break;
        }
        for (int i = 0; i < n_nw; ++i) {
            ans[c_nw + i][c_nw] = ans[c_nw + i][m - c_nw - 1] = c_nw;
        }
        for (int i = 0; i < m_nw; ++i) {
            ans[c_nw][c_nw + i] = ans[n - c_nw - 1][c_nw + i] = c_nw;
        }
        c_nw++;
        n_nw -= 2;
        m_nw -= 2;
    }
    if (c_nw != k) {
        int cnt_nw = c_nw + (n_nw / 2) * (m_nw / 2);
        int d = cnt_nw - k;
        if (d == n_nw / 2 + m_nw / 2 - 1) {
            if (min(n_nw, m_nw) >= 8) {
                if (n_nw < m_nw) {
                    int d2 = min(m_nw / 2, d);
                    swap(d, d2);
                    d2 -= d;
                    if (d2 == 1) {
                        d--;
                        d2++;
                    }
                    for (int i = 0; i < d * 2; ++i) {
                        ans[c_nw][c_nw + i] = ans[c_nw + 3][c_nw + i] = c_nw;
                    }
                    ans[c_nw + 1][c_nw] = ans[c_nw + 2][c_nw] = ans[c_nw + 1][c_nw + d * 2 - 1] = ans[c_nw + 2][c_nw + d * 2 - 1] = c_nw;
                    if (d2 > 0) {
                        d = d2;
                        for (int i = 0; i < d * 2; ++i) {
                            ans[c_nw + 4][c_nw + i] = ans[c_nw + 7][c_nw + i] = c_nw + 1;
                        }
                        ans[c_nw + 5][c_nw] = ans[c_nw + 6][c_nw] = ans[c_nw + 5][c_nw + d * 2 - 1] = ans[c_nw + 6][c_nw + d * 2 - 1] = c_nw + 1;
                        c_nw++;
                    }
                    c_nw++;
                } else {
                    int d2 = min(n_nw / 2, d);
                    swap(d, d2);
                    d2 -= d;
                    if (d2 == 1) {
                        d--;
                        d2++;
                    }
                    for (int i = 0; i < d * 2; ++i) {
                        ans[c_nw + i][c_nw] = ans[c_nw + i][c_nw + 3] = c_nw;
                    }
                    ans[c_nw][c_nw + 1] = ans[c_nw][c_nw + 2] = ans[c_nw + d * 2 - 1][c_nw + 1] = ans[c_nw + d * 2 - 1][c_nw + 2] = c_nw;
                    if (d2 > 0) {
                        d = d2;
                        for (int i = 0; i < d * 2; ++i) {
                            ans[c_nw + i][c_nw + 4] = ans[c_nw + i][c_nw + 7] = c_nw + 1;
                        }
                        ans[c_nw][c_nw + 5] = ans[c_nw][c_nw + 6] = ans[c_nw + d * 2 - 1][c_nw + 5] = ans[c_nw + d * 2 - 1][c_nw + 6] = c_nw + 1;
                        c_nw++;
                    }
                    c_nw++;
                }
            } else {
                if (n_nw == 6 && m_nw == 6) {
                    cout << "NO\n";
                    return;
                }
                if (n_nw == 6) {
                    for (int i = 0; i < 6; ++i) {
                        ans[c_nw + i][c_nw] = ans[c_nw + i][c_nw + 3] = c_nw;
                    }
                    for (int i = 1; i < 3; ++i) {
                        ans[c_nw][c_nw + i] = ans[c_nw + 5][c_nw + i] = c_nw;
                    }
                    for (int i = 4; i < m_nw; ++i) {
                        ans[c_nw][c_nw + i] = ans[c_nw + 5][c_nw + i] = c_nw + 1;
                    }
                    for (int i = 1; i < 5; ++i) {
                        ans[c_nw + i][c_nw + 4] = ans[c_nw + i][c_nw + m_nw - 1] = c_nw + 1;
                    }
                    c_nw += 2;
                } else {
                    for (int i = 0; i < 6; ++i) {
                        ans[c_nw][c_nw + i] = ans[c_nw + 3][c_nw + i] = c_nw;
                    }
                    for (int i = 1; i < 3; ++i) {
                        ans[c_nw + i][c_nw] = ans[c_nw + i][c_nw + 5] = c_nw;
                    }
                    for (int i = 4; i < n_nw; ++i) {
                        ans[c_nw + i][c_nw] = ans[c_nw + i][c_nw + 5] = c_nw + 1;
                    }
                    for (int i = 1; i < 5; ++i) {
                        ans[c_nw + 4][c_nw + i] = ans[c_nw + n_nw - 1][c_nw + i] = c_nw + 1;
                    }
                    c_nw += 2;
                }
            }
        } else {
            int h = n_nw / 2, w = m_nw / 2;
            while (h + w - 2 > d) {
                if (h > w) {
                    h--;
                } else {
                    w--;
                }
            }
            for (int i = 0; i < h * 2; ++i) {
                ans[c_nw + i][c_nw] = ans[c_nw + i][c_nw + w * 2 - 1] = c_nw;
            }
            for (int i = 1; i + 1 < w * 2; ++i) {
                ans[c_nw][c_nw + i] = ans[c_nw + h * 2 - 1][c_nw + i] = c_nw;
            }
            c_nw++;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (ans[i][j] == -1) {
                ans[i][j] = ans[i][j + 1] = ans[i + 1][j] = ans[i + 1][j + 1] = c_nw;
                c_nw++;
            }
        }
    }
    cout << "YES\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << ans[i][j] + 1 << ' ';
        }
        cout << '\n';
    }
    return;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 18 / 18
• Subtask 5: 39 / 39
• Subtask 6: 22 / 22