Submission #498644

#	Time	Username	Problem	Language	Result	Execution time	Memory
498644		model_code	Gardening (RMI21_gardening)	C++17	100 / 100	54 ms	924 KiB

Main

// gardening_100_tamio.cpp
#include <bits/stdc++.h>
using namespace std;

// 38 6 36

template <typename T>
void build(int n, int m, int k, T it) {
    auto print_rect = [&](int i0, int i1, int j0, int j1) {
        for (int i = i0; i <= i1; ++i) it[i][j0] = it[i][j1] = k;
        for (int j = j0; j <= j1; ++j) it[i0][j] = it[i1][j] = k;
        --k;
    };

    auto do_all_sq = [&]() {
        for (int i = 0; i < n; ++i)
            for (int j = 0
            ; j < m; ++j)
                if (it[i][j] == 0) print_rect(i, i + 1, j, j + 1);
    };

    int critical = ((n - 2) / 2) * ((m - 2) / 2) + 1;

    if (k == (n / 2) * m / 2)
        do_all_sq();
    else if (k > critical) {
        int diff = k - critical, diff_i = min(diff, (n - 4) / 2),
            diff_j = diff - diff_i;

        print_rect(0, n - 2 * diff_i - 1, 0, m - 2 * diff_j - 1);
        do_all_sq();
    } else if (k == critical - 1) {
        if (n < m) {
            print_rect(0, n - 1, 0, m - 3);
            print_rect(1, 4, 1, 4);
            do_all_sq();
        } else {
            print_rect(0, n - 3, 0, m - 1);
            print_rect(1, 4, 1, 4);
            do_all_sq();
        }
    } else {
        print_rect(0, n - 1, 0, m - 1);

        for (int i = 0; i < n; ++i) ++it[i];

        build(n - 2, m - 2, k, it + 1);
    }
}

#ifdef TESTING

#define DEF_ENV(name) int env_##name = atoi(getenv(#name))

#endif

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

#ifdef TESTING
    long long s = 0;

    DEF_ENV(N);
    DEF_ENV(M);
    DEF_ENV(eq);
#endif

    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;

#ifdef TESTING
        assert(1 <= n && n <= 200000);
        assert(1 <= m && m <= 200000);
        assert(1 <= k && k <= (long long)n * m);

        assert(1 <= n && n <= env_N);
        assert(1 <= m && m <= env_M);
        assert(!env_eq || n == m);
#endif
        if (n % 2 == 1 || m % 2 == 1 || k < max(n / 2, m / 2) ||
            k > (n / 2) * (m / 2) || k == (n / 2) * (m / 2) - 1 ||
            (n == m && k == n / 2 + 1))
            cout << "NO\n";
        else {
            cout << "YES\n";
#ifdef TESTING
            s += (long long)n * m;
            assert(s <= 200000);
#endif
            vector<vector<int>> buf(n, vector<int>(m, 0));

            vector<vector<int>::iterator> its;

            transform(begin(buf), end(buf), back_inserter(its),
                      [](vector<int>& v) { return begin(v); });

            build(n, m, k, begin(its));

            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) cout << buf[i][j] << ' ';
                cout << '\n';
            }
            cout << flush;
        }
    }

    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